Binary search is more than just searching a sorted array. It's a thinking pattern that applies to a huge range of problems.
Binary search finds a target in a sorted array by repeatedly halving the search space. Each step eliminates half the remaining elements.
Array: [1, 3, 5, 7, 9, 11, 13]
Target: 7
Step 1: mid = 5 → 7 > 5 → search right half
Step 2: mid = 9 → 7 < 9 → search left half
Step 3: mid = 7 → found!
Time: O(log n) — 1 billion elements needs only ~30 comparisons.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # avoids integer overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # target is in right half
else:
right = mid - 1 # target is in left half
return -1 # not founddef first_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # keep searching left
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return resultdef last_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # keep searching right
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return resultThis is the most powerful pattern — binary search on a value range, not an array index.
def ship_within_days(weights, days):
# Binary search on capacity (answer range)
left = max(weights) # minimum possible capacity
right = sum(weights) # maximum possible capacity
def can_ship(capacity):
days_needed, current = 1, 0
for w in weights:
if current + w > capacity:
days_needed += 1
current = 0
current += w
return days_needed <= days
while left < right:
mid = (left + right) // 2
if can_ship(mid):
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
# Left half is sorted
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if arr[mid] < target <= arr[right]:
Ask yourself: "Is there a monotonic condition I can binary search on?"
| Problem type | Binary search on |
|---|---|
| Find element in sorted array | Index |
| Find minimum valid value | Answer range |
| Find first/last occurrence | Index with boundary tracking |
| Minimize maximum / Maximize minimum | Answer range |
| Kth smallest/largest | Value range |
mid = left + (right - left) // 2 to avoid overflow