Examples / Binary search▶Run in PyTrace
Binary Search Visualization in Python
Binary search finds a value in a sorted array by comparing it with the middle element and discarding the half where it cannot be. Each step halves the search space, so even a million elements need only about 20 comparisons.
The classic bugs are off-by-one errors: lo <= hi versus lo < hi, and mid + 1 versus mid. Stepping through the loop and watching the three pointers makes it obvious when the range stops shrinking.
ComplexityO(log n) time, O(1) extra space.
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Inputs
nums[-1,0,3,5,9,12,17,21,30,42]
target21
expected7
What to watch
lo,midandhias pointers overnums- The comparison
nums[mid] < targetthat decides which half to keep - How few iterations it takes to reach the target