Binary Search

Analogy categoryAnalogies

Introduction

Binary search finds the position of a target value within a SORTED array by repeatedly comparing the target to the middle element and eliminating half the remaining search space each time. It requires the input to be sorted beforehand (sorting costs O(n log n) if not already sorted), but once sorted, lookups run in O(log n) time, dramatically faster than the O(n) of linear search for large datasets.

🏏

Cricket analogy: Binary search on a sorted list of career batting averages is like finding a specific score by repeatedly checking the middle name of an alphabetized squad sheet and eliminating half the names each time, taking O(log n) checks instead of scanning all 11 names one by one.

Algorithm/Syntax

python

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

Explanation

The algorithm maintains two pointers, lo and hi, that bound the current search range [lo, hi]. Each iteration computes mid and compares arr[mid] to the target: if equal, we're done; if arr[mid] is smaller, the target must be in the right half so lo becomes mid+1; if larger, the target must be in the left half so hi becomes mid-1. The loop invariant is that the target, if present, always lies within [lo, hi]. The loop terminates when lo > hi, meaning the search space is empty and the target is absent. Using lo + (hi - lo) // 2 instead of (lo + hi) // 2 avoids integer overflow in languages with fixed-width integers (not an issue in Python, but a common interview point). Off-by-one errors are the most common bug: using < instead of <= in the while condition, or forgetting the +1/-1 when updating lo/hi, causes infinite loops or missed elements.

🏏

Cricket analogy: The lo/hi bounds in binary search are like a stats analyst narrowing which over a boundary was hit in, starting from over 1 and over 50 and halving the range each guess; comparing against the wicket-keeper's shout of 'too early' or 'too late' updates lo or hi until they cross and the search ends.

Example

python

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

# Trace: arr = [1, 3, 5, 7, 9, 11], target = 7
# lo=0, hi=5 -> mid=2, arr[2]=5 < 7 -> lo=3
# lo=3, hi=5 -> mid=4, arr[4]=9 > 7 -> hi=3
# lo=3, hi=3 -> mid=3, arr[3]=7 == 7 -> return 3
print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))  # -1 (not found)

Complexity

Binary search runs in O(log n) time because each comparison halves the search space, requiring at most ceil(log2(n+1)) iterations. Space complexity is O(1) for the iterative version shown, or O(log n) for a recursive version due to call stack depth. The precondition is critical: the array must already be sorted; searching an unsorted array with binary search gives incorrect results silently.

🏏

Cricket analogy: Binary search through a sorted list of career averages runs in O(log n) because each comparison halves the remaining candidates, needing at most about log2(n+1) checks even for a database of thousands of players; but the list must already be sorted by average, or a search silently returns a wrong player.

Key Takeaways

Binary search requires a sorted array and runs in O(log n) time, O(1) space iteratively.
The invariant lo <= hi defines the active search range; the loop ends when it's empty.
Common bugs: wrong loop condition (< vs <=), forgetting +1/-1 on pointer updates, causing infinite loops or off-by-one misses.
Binary search variants can find the first/last occurrence, insertion point, or search in rotated sorted arrays.

Practice what you learned

1. What precondition must hold for binary search to work correctly?

2. What is the time complexity of binary search on an array of n elements?

3. In the iterative binary search, what does 'lo + (hi - lo) // 2' compute compared to '(lo + hi) // 2'?

4. What causes an infinite loop in a buggy binary search implementation?

5. What is the space complexity of the standard iterative binary search?

Was this page helpful?

Heap Sort and Counting Sort

Searching Algorithms Comparison

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#BinarySearch#Binary#Search#Algorithm#Syntax#StudyNotes#SkillVeris