Binary Search
Learn how binary search eliminates half the search space with every comparison to find any value in O(log n).
Binary Search
Binary search works on sorted arrays by repeatedly halving the search space. Compare the target against the middle element — if they match, done. If the target is smaller, search the left half. If larger, search the right half. Each comparison eliminates half the remaining elements.
This is the same principle as guessing a number between 1 and 100 — always guess the midpoint. After 7 guesses you can pinpoint any number. That is O(log₂ 100) ≈ 7.
How it works
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # found
elif arr[mid] < target:
left = mid + 1 # search right half
else:
right = mid - 1 # search left half
return -1 # not found
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(arr, 13)) # 6
print(binary_search(arr, 4)) # -1Why mid = left + (right - left) // 2
Both (left + right) // 2 and left + (right - left) // 2 give the same result in Python, since Python has arbitrary-precision integers. But in languages like C and Java, left + right can overflow if both are large. The safer formula avoids this and is worth using as a habit.
Recursive version
def binary_search_recursive(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1 # base case — empty search space
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)Finding insertion position
bisect from Python's standard library finds where an element would be inserted to keep the array sorted — O(log n).
import bisect
arr = [1, 3, 5, 7, 9]
# index where 6 would be inserted
pos = bisect.bisect_left(arr, 6) # 3
# check if element exists at that position
if pos < len(arr) and arr[pos] == 6:
print("found")
else:
print("not found, would insert at", pos)
# insert 6 and keep sorted
bisect.insort(arr, 6)
print(arr) # [1, 3, 5, 6, 7, 9]Binary search on the answer
Beyond searching arrays, binary search applies to any problem where the answer space is monotone — answers go from "no" to "yes" at some threshold. Search for that threshold.
# problem: find the minimum capacity C such that
# you can ship all packages within D days
def can_ship(weights, D, capacity):
days = 1
current = 0
for w in weights:
if current + w > capacity:
days += 1
current = 0
current += w
return days <= D
def min_ship_capacity(weights, D):
lo = max(weights) # minimum possible — must fit heaviest
hi = sum(weights) # maximum possible — ship all in one day
while lo < hi:
mid = (lo + hi) // 2
if can_ship(weights, D, mid):
hi = mid # try smaller
else:
lo = mid + 1 # need bigger
return lo"Binary search on the answer" is one of the most powerful patterns in competitive programming and advanced interviews. Any time a problem asks for the minimum or maximum value satisfying a condition — and you can efficiently check whether a given value satisfies it — binary search on the answer in O(log n) passes.
Complexity
| Case | Time | Space (iterative) |
|---|---|---|
| Best (target is mid) | O(1) | O(1) |
| Average | O(log n) | O(1) |
| Worst | O(log n) | O(1) |