Binary search is one of the most powerful techniques in algorithm design. It reduces O(n) searches to O(log n) by cutting the search space in half at every step. In this article, you will learn the classic binary search, common templates, search on answer, and rotated array problems.
We show every example in Kotlin, Python, and Go.
Classic Binary Search
Given a sorted array and a target value, find the target’s index or return -1.
Python:
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoid overflow
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Kotlin:
fun binarySearch(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
when {
nums[mid] == target -> return mid
nums[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return -1
}
Go:
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
Time: O(log n). Space: O(1).
Why left + (right - left) / 2 instead of (left + right) / 2? Because left + right can overflow in languages with fixed-size integers (Kotlin, Go, Java, C++). In Python this is not a problem because integers can be arbitrarily large, but it is a good habit to use the safe formula.
Binary Search Templates
There are two common templates. Knowing when to use each one prevents off-by-one errors.
Template 1: Find Exact Match (left <= right)
Use when you are looking for a specific value.
def find_exact(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Template 2: Find Boundary (left < right)
Use when you need to find the first or last position that satisfies a condition.
# Find the first element >= target (lower bound)
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# Find the first element > target (upper bound)
def upper_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return left
Kotlin:
fun lowerBound(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size
while (left < right) {
val mid = left + (right - left) / 2
if (nums[mid] < target) left = mid + 1
else right = mid
}
return left
}
Go:
func lowerBound(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
Finding First and Last Position
Given a sorted array with duplicates, find the first and last position of a target.
Python:
def search_range(nums, target):
first = lower_bound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
last = upper_bound(nums, target) - 1
return [first, last]
# Example: nums = [5,7,7,8,8,10], target = 8
# lower_bound returns 3, upper_bound returns 5
# Result: [3, 4]
Binary Search on Answer
This is the most powerful technique. Instead of searching in an array, you search in a range of possible answers.
The pattern:
- Define the search space: what is the minimum and maximum possible answer?
- For each candidate answer (mid), check if it is feasible
- Narrow the search space based on feasibility
Koko Eating Bananas
Koko has n piles of bananas. She can eat at speed k (bananas per hour). She has h hours. Find the minimum k.
Python:
import math
def min_eating_speed(piles, h):
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
# Can Koko finish all piles at speed mid in h hours?
hours_needed = sum(math.ceil(pile / mid) for pile in piles)
if hours_needed <= h:
right = mid # mid is fast enough, try slower
else:
left = mid + 1 # mid is too slow, try faster
return left
Kotlin:
fun minEatingSpeed(piles: IntArray, h: Int): Int {
var left = 1
var right = piles.max()
while (left < right) {
val mid = left + (right - left) / 2
val hoursNeeded = piles.sumOf { (it + mid - 1) / mid }
if (hoursNeeded <= h) right = mid
else left = mid + 1
}
return left
}
Go:
func minEatingSpeed(piles []int, h int) int {
left, right := 1, 0
for _, p := range piles {
if p > right {
right = p
}
}
for left < right {
mid := left + (right-left)/2
hours := 0
for _, p := range piles {
hours += (p + mid - 1) / mid
}
if hours <= h {
right = mid
} else {
left = mid + 1
}
}
return left
}
Time: O(n * log(max(piles))). The binary search runs log(max) times, and each check takes O(n).
Search in Rotated Sorted Array
A sorted array is rotated at some pivot. For example, [4,5,6,7,0,1,2] was [0,1,2,4,5,6,7] rotated at index 4. Find a target value.
The key insight: at least one half of the array is always sorted.
Python:
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Kotlin:
fun searchRotated(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
if (nums[mid] == target) return mid
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) right = mid - 1
else left = mid + 1
} else {
if (target > nums[mid] && target <= nums[right]) left = mid + 1
else right = mid - 1
}
}
return -1
}
Go:
func searchRotated(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[left] <= nums[mid] {
if target >= nums[left] && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if target > nums[mid] && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
Time: O(log n). Space: O(1).
Find Minimum in Rotated Sorted Array
Python:
def find_min_rotated(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1 # Minimum is in the right half
else:
right = mid # Minimum is in the left half (including mid)
return nums[left]
Search in 2D Matrix
A sorted 2D matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. Treat it as a single sorted array.
Python:
def search_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
row, col = mid // cols, mid % cols
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
left = mid + 1
else:
right = mid - 1
return False
Time: O(log(m * n)). Space: O(1).
How to Recognize Binary Search Problems
Ask yourself these questions:
- Is the data sorted? Classic binary search.
- Can I define a search space of possible answers? Binary search on answer.
- Is there a monotonic property? If “yes” for x implies “yes” for all x+1, use binary search to find the boundary.
- Does the problem ask for “minimum of maximum” or “maximum of minimum”? Almost always binary search on answer.
Common Mistakes
Off-by-one errors. The most common binary search bug. Use a template and stick to it.
Integer overflow in mid calculation. Always use
left + (right - left) / 2.Wrong loop condition. Use
left <= rightfor exact match,left < rightfor boundary finding.Not considering edge cases. Empty array, single element, target not in array, all elements are the same.
Confusing the two templates. Template 1 finds a value. Template 2 finds a boundary. Mixing them causes infinite loops.
Practice Problems
| Problem | Type | LeetCode # |
|---|---|---|
| Binary Search | Exact match | #704 |
| Search in Rotated Sorted Array | Modified search | #33 |
| Find Minimum in Rotated Sorted Array | Boundary | #153 |
| First and Last Position | Boundary | #34 |
| Search a 2D Matrix | Flattened search | #74 |
| Koko Eating Bananas | Search on answer | #875 |
| Capacity to Ship Packages | Search on answer | #1011 |
What’s Next?
Binary search often works on sorted data. But what about unsorted arrays? The next article covers Two Pointers and Sliding Window — two techniques that solve array problems in O(n) time without sorting.
Next: DSA Tutorial #14: Two Pointers and Sliding Window
Full series: DSA from Zero to Interview Ready