Binary Search

After this lesson, you will be able to: Implement binary search iteratively and recursively, understand why it requires sorted input, and handle the leftmost/rightmost variations.

Binary search is the canonical O(log n) algorithm and the simplest demonstration of divide and conquer. It also hides a surprising number of bugs, which is why interviewers love it.

Prerequisites:Big O Notation

The idea: halve the search space each step

Binary search finds a target in a sorted array by repeatedly checking the middle element. If the middle equals the target, done. If the target is smaller, discard the right half; if larger, discard the left half. Each step throws away half the remaining elements, so it finds anything in about log n steps. Searching a million sorted items takes around 20 comparisons instead of up to a million.

Iterative binary search

The version you should be able to write without thinking.

python

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                  # note: <= , not <
        mid = lo + (hi - lo) // 2     # avoids overflow in other languages
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                        # not found

# arr MUST be sorted. binary_search([1,3,5,7,9], 7) -> index 3

Recursive binary search

Same logic, expressed with the call stack.

python

def binary_search_rec(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1                    # base case: empty range
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    return binary_search_rec(arr, target, lo, mid - 1)

Why it requires sorted input

Binary search only works because sortedness lets you decide which half to discard. If the array is unsorted, knowing the middle value tells you nothing about where the target is, so you cannot eliminate half. If you need to search an unsorted array once, a linear O(n) scan is correct; sorting first only pays off if you will search many times (sort once O(n log n), then each search is O(log n)).

Common mistakes only experienced devs catch

Using < instead of <= in the loop condition, missing the last element. Computing mid as (lo + hi) // 2, which can overflow in fixed-width-integer languages (use lo + (hi - lo) // 2). Infinite loops from updating lo = mid instead of mid + 1. Running binary search on unsorted data and getting silent wrong answers. Forgetting that the leftmost/rightmost variants need you to keep searching after a match instead of returning immediately.

←Big O Notation

Back to Algorithms

Sorting Algorithms→