Classic Binary Search: Left, Right, Mid
Implement binary search iteratively and recursively, nail the off-by-one details for lo/hi boundaries, and verify correctness with edge-case inputs.
Why Binary Search Matters
Binary search reduces an O(n) linear scan to O(log n) by halving the search space at every step. In an array of one million elements a linear scan needs up to 1,000,000 comparisons, but binary search needs at most 20. This efficiency makes it one of the most commonly tested algorithms in coding interviews.
The core insight is that a sorted array lets you decide, after a single comparison, which half of the remaining data to discard entirely.
The Left, Mid, Right Framework
Binary search uses three index pointers: lo (left boundary), hi (right boundary), and mid (midpoint). At each iteration you compute mid = (lo + hi) // 2 and compare the target against arr[mid]. If the target is smaller, move hi = mid - 1; if larger, move lo = mid + 1; if equal, you found it.
The loop continues while lo <= hi. When the loop exits without finding the target, return -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1All lessons in this course
- Classic Binary Search: Left, Right, Mid
- Binary Search on Rotated and Unsorted Arrays
- Lower Bound and Upper Bound
- Answer-Space Binary Search