Search Algorithms

Binary Search

● Beginner ⏱ 8 min read search

Binary search finds a target in a sorted array in O(log n) time by repeatedly halving the search space. Each comparison eliminates half the remaining elements, so 1 billion elements need at most 30 comparisons.

How It Works

Text

Sorted array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Target: 7

lo=0, hi=9  → mid=4  → arr[4]=9  → 7 < 9  → hi=3
lo=0, hi=3  → mid=1  → arr[1]=3  → 7 > 3  → lo=2
lo=2, hi=3  → mid=2  → arr[2]=5  → 7 > 5  → lo=3
lo=3, hi=3  → mid=3  → arr[3]=7  → Found! return 3

4 comparisons to search 10 elements vs 7 for linear search.

Iterative Implementation

Python

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2     # avoids integer overflow (safe in Python too)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 6))    # -1

Recursive Implementation

Python

def binary_search_recursive(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, hi)
    else:
        return binary_search_recursive(arr, target, lo, mid - 1)

print(binary_search_recursive(nums, 13))  # 6

Python bisect Module

The bisect module provides production-ready binary search. Prefer it over hand-rolled implementations.

Python

import bisect

nums = [1, 3, 5, 7, 9, 11, 13]

# bisect_left: index where target would be inserted (leftmost)
idx = bisect.bisect_left(nums, 7)
print(idx)                        # 3
print(nums[idx] == 7)             # True — target found at idx

# bisect_right: index after all equal elements
print(bisect.bisect_right(nums, 7))  # 4

# insort: insert and keep sorted — O(n) due to shifting
bisect.insort(nums, 6)
print(nums)   # [1, 3, 5, 6, 7, 9, 11, 13]

# Clean lookup helper using bisect_left
def contains(sorted_arr, target):
    idx = bisect.bisect_left(sorted_arr, target)
    return idx < len(sorted_arr) and sorted_arr[idx] == target

Left & Right Boundary Variants

In arrays with duplicates, you often need the first or last occurrence of a target.

Python

arr = [1, 2, 2, 2, 3, 4]

# First occurrence of target (left boundary)
def find_first(arr, target):
    lo, hi = 0, len(arr) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid          # record, but keep searching left
            hi = mid - 1
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

# Last occurrence of target (right boundary)
def find_last(arr, target):
    lo, hi = 0, len(arr) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid          # record, but keep searching right
            lo = mid + 1
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(find_first(arr, 2))   # 1
print(find_last(arr, 2))    # 3

Off-by-one Pitfalls

⚠️

Common binary search bugs

Always use lo <= hi (not lo < hi) so the single-element case is checked. Use hi = mid - 1 and lo = mid + 1 (not mid) to avoid infinite loops when lo == hi. Compute mid as lo + (hi - lo) // 2 rather than (lo + hi) // 2 — the latter can overflow in languages with fixed-width integers.

Complexity Table

Case	Time	Space	Note
Best case	O(1)	O(1)	Target at midpoint first try
Average / Worst case	O(log n)	O(1) iterative	Halves search space each step
Recursive	O(log n)	O(log n)	Call stack depth
Requirement	—	—	Array must be sorted