Skip to main content

Subjects

Binary Search — Finding Anything in O(log n)

binary-searchalgorithmssearchingbeginnerfree
The most important search algorithm in CS — how binary search halves the search space with every comparison.
Share:

What Is Binary Search?

Binary search finds a target value in a sorted array by repeatedly halving the search range. It is the reason we can search a phone book of a million entries in about 20 steps.

The key requirement: the array must be sorted. If it’s not, binary search gives nonsense results.

How It Works

  1. Set low = 0 and high = len(arr) - 1.
  2. Compute mid = (low + high) // 2.
  3. If arr[mid] == target, return mid.
  4. If arr[mid] < target, the target must be in the right half. Set low = mid + 1.
  5. If arr[mid] > target, the target must be in the left half. Set high = mid - 1.
  6. Repeat until low > high (not found).

Each iteration eliminates half the remaining elements. That is why it is O(log n).

python
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if arr[mid] == target:
            print(f"Found {target} at index {mid} in {steps} steps")
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    print(f"{target} not found after {steps} steps")
    return -1

sorted_arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
binary_search(sorted_arr, 23)
binary_search(sorted_arr, 50)

import math
print(f"\nArray size: {len(sorted_arr)}")
print(f"Max steps (log2): {math.ceil(math.log2(len(sorted_arr)))}")
Binary search vs linear search
MetricBinary SearchLinear Search
TimeO(log n)O(n)
PrerequisiteSorted arrayNone
n=1,000~10 comparisons~1,000 comparisons
n=1,000,000~20 comparisons~1,000,000 comparisons
SpaceO(1) iterativeO(1)

Key Takeaways

  • Binary search requires a sorted array. Unsorted = wrong answers.
  • Each comparison eliminates half the remaining elements — O(log n).
  • A million elements? About 20 comparisons. A billion? About 30.
  • Watch for off-by-one errors in the boundary conditions. low <= high (not <) is correct.
  • Binary search appears in database indexes, Git bisect, and Python’s bisect module.