Binary Search: Finding a Needle in a Haystack

The problem hiding in a results portal

Every year, when CBSE Class 12 results go live, lakhs of students hit a portal within the same hour, each typing in one roll number and expecting an answer in under a second. Suppose, purely for illustration, that a portal like this holds twenty-one lakh (21,00,000) roll numbers, stored in sorted order because that is how databases index numeric keys. If the lookup routine behind that portal scanned the list one entry at a time, starting from the first roll number and checking each one until it found a match, the worst case would be twenty-one lakh comparisons for a single student, and the server would need to do this for every one of those lakhs of students within minutes. That does not happen, and the reason it does not happen is a fifty-year-old idea that this chapter builds from first principles: binary search. Instead of checking every entry, binary search exploits the fact that the list is sorted to throw away half the remaining candidates with a single comparison. As you will derive precisely in a few paragraphs, that same twenty-one-lakh-entry lookup drops from twenty-one lakh comparisons to at most twenty-two. That is not a rough estimate; it falls out of the mathematics of halving, and by the end of this chapter you will be able to derive it yourself for any input size.

Why sortedness is the whole trick

Binary search answers one specific question: given a sorted array arr and a target value, find an index i such that arr[i] == target, or report that no such index exists. The single non-negotiable precondition is that arr is sorted, conventionally in non-decreasing order. Nothing about binary search works without this. Sortedness is what lets you look at one element, arr[mid], compare it to the target, and legally discard an entire half of the array based on that one comparison. If arr[mid] is less than the target, every element to the left of mid is also less than the target (because the array is sorted), so none of them can equal the target, and the left half can be discarded outright. If arr[mid] is greater than the target, the symmetric argument discards the right half. This is the entire algorithm: maintain a search window [lo, hi], and at each step, use one comparison at the midpoint to halve that window. The loop invariant, the fact you can prove stays true before and after every iteration, is: if the target exists in arr, it exists within arr[lo..hi]. The loop terminates either by finding the target or by lo crossing past hi, at which point the invariant tells you the target cannot be present, because the window that was guaranteed to contain it has shrunk to nothing.

The algorithm, precisely

Here is the iterative version, written so that lo and hi are always valid indices into arr, and the window [lo, hi] is inclusive on both ends:

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

Three details here are load-bearing, not stylistic. First, the loop condition is lo <= hi, not lo < hi; a window with lo == hi still contains exactly one unexamined element, and dropping that check is a classic source of the "misses the last element" bug. Second, on a miss the boundary moves to mid + 1 or mid - 1, never to mid itself; if you set, say, hi = mid instead of hi = mid - 1, the window never shrinks past a certain point and the loop can run forever. Third, mid = (lo + hi) // 2 always lands inside the current window because lo <= hi guarantees lo <= mid <= hi, so the window is strictly smaller on every iteration and the loop is guaranteed to terminate.

A fully worked trace

Take the sorted array of sixteen multiples of five, indices 0 through 15:

index:  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
value:  5  10  15  20  25  30  35  40  45  50  55  60  65  70  75  80

Search for target = 65. Trace the window and the comparison at each step:

Step 1: lo=0,  hi=15, mid=7  -> arr[7]=40  < 65, so lo = 8
Step 2: lo=8,  hi=15, mid=11 -> arr[11]=60 < 65, so lo = 12
Step 3: lo=12, hi=15, mid=13 -> arr[13]=70 > 65, so hi = 12
Step 4: lo=12, hi=12, mid=12 -> arr[12]=65 == 65, return 12

Four comparisons locate the target among sixteen elements. The diagram below renders this exact trace: each row is one iteration, the pale blue band marks the current window [lo, hi], grey cells are indices already eliminated from consideration, and the dark blue cell is the midpoint being compared in that step.

You can check the trace against running code rather than trusting it by eye. This is the same iterative function from above, instrumented to count comparisons:

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

arr = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80]
print(binary_search(arr, 65))

This prints (12, 4): index 12, reached in 4 comparisons, matching the trace exactly.

How fast, exactly? Deriving O(log n)

Every iteration of binary search does a constant amount of work (one comparison, one arithmetic update) and then operates on a window that is, at worst, half the size of the previous one. Written as a recurrence for the worst-case running time T(n) on an array of size n, this is:

T(n) = T(n/2) + O(1),   T(1) = O(1)

You can solve this by unrolling it. After one halving the remaining size is n/2; after two halvings, n/4; after k halvings, n/2^k. The recursion bottoms out when the remaining size reaches 1, i.e. when n/2^k = 1, which gives k = log2(n). Since each of those k steps did O(1) work, the total work is O(log n). The same answer falls out of the master theorem: for T(n) = aT(n/b) + f(n) with a = 1, b = 2, and f(n) = O(1) = O(n^0), compute log_b(a) = log2(1) = 0. Since f(n) = Theta(n^0) matches n^{log_b a} exactly (case 2 of the theorem, with the polylog exponent k = 0), the solution is T(n) = Theta(n^0 * log(n)) = Theta(log n). Both derivations agree: binary search does at most ceil(log2 n) comparisons in the worst case, where ceil rounds up to the nearest integer because the number of halvings must be a whole number of loop iterations.

That bound is exact, not approximate, and you can verify it directly from powers of two: ceil(log2 n) is the smallest integer k such that n <= 2^k. The table below applies this to a range of input sizes, alongside the worst case for a plain left-to-right linear scan, which needs up to n comparisons.

The last row is the results-portal number from the opening of this chapter: with twenty-one lakh sorted roll numbers, binary search never needs more than 22 comparisons, because 2^21 = 20,97,152 is just under twenty-one lakh and 2^22 = 41,94,304 comfortably clears it, so ceil(log2(21,00,000)) = 22. This is also why binary search barely notices growth: doubling the input from n to 2n adds exactly one comparison to the worst case, because log2(2n) = log2(n) + 1. A linear scan, by contrast, doubles its own worst case whenever n doubles. That single algebraic fact, that logarithms turn multiplication of the input into addition of one comparison, is the entire reason binary search scales to database indexes with billions of rows without becoming slow.

The recursive form, and its hidden cost

Binary search is often written recursively, and the translation from the iterative loop is direct: each recursive call narrows the window exactly the way each loop iteration did.

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) // 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(arr, 65))

Run against the same sixteen-element array, this prints 12, the same index the iterative version found. The two versions do identical work, comparison for comparison, and both run in O(log n) time. Where they differ is space. The iterative version uses a fixed number of variables (lo, hi, mid) regardless of array size, so its space complexity is O(1). The recursive version, however, pushes one stack frame per call before it can return, and the recursion depth is exactly the number of halvings, O(log n). For an array of a million elements that is about twenty stack frames, harmless in practice, but it is a real cost that the iterative version does not pay, and it is worth knowing which one you are choosing and why.

A common misconception: "binary search is always the better choice"

Because O(log n) so obviously beats O(n) on a growth chart, students often conclude that binary search should replace linear search whenever possible. This misconception ignores where the data comes from. Binary search's O(log n) bound assumes the array is already sorted. If it is not, and you only need to answer a single query, you have to pay for sorting before you can binary search at all, and that changes the comparison completely.

A comparison-based sort (mergesort, for example) needs on the order of n * log2(n) comparisons in the worst case. For n = 1,000, that is 1000 * log2(1000) ≈ 1000 * 9.97 ≈ 9,966 comparisons just to sort, and then roughly 10 more to binary search inside the sorted result, for a total near 9,976 comparisons. A plain linear scan of the same 1,000 unsorted elements costs at most 1,000 comparisons. Sorting first to enable one binary search is roughly ten times more expensive than just scanning, for this input size, and the gap only widens as n grows, because n log n always outpaces a single linear pass. The corrected rule is: binary search wins decisively when the data is already sorted, or when you can amortize a one-time sort across many repeated queries on the same data (which is exactly what a database index does, sorting once and then serving lakhs of lookups against that same structure). It is not a free upgrade over linear search for a one-off search over unsorted data.

Beyond arrays: binary search on a predicate

The core idea of binary search generalizes past arrays of numbers. What binary search really needs is a search space where a boolean condition is monotonic, false for a while and then true for the rest (or vice versa), so that testing the midpoint always tells you which half can be discarded. A widely used real instance of this is git bisect, a command built into Git for finding which commit in a project's history introduced a bug. Given a commit known to be good and a later commit known to be bad, git bisect does not test every commit in between one by one. It checks out the middle commit of the range, asks whether it is good or bad, and discards half the remaining commits based on the answer, exactly as binary search discards half an array based on one comparison. The precondition here is the same monotonicity that sortedness provided for arrays: the assumption is that once the bug appears, it stays present in every commit after that (the predicate "is this commit bad" is false, then true, and does not flip back and forth). For a history of a thousand commits, this finds the offending commit in about ten checks instead of up to a thousand, the same log2(n) speedup derived above, just applied to commits instead of array indices.

A closely related technique, common in algorithmic problem solving, is called binary search on the answer. Instead of searching for a value that exists in an array, you search over a range of candidate answers to an optimization problem, using a monotonic yes/no test at each candidate. For instance, given a way to test "can this be done within a budget of x," where the answer flips from no to yes as x increases, you can binary search over x directly to find the smallest budget for which the answer is yes, without ever needing to store or sort the candidate values as an array. The mechanism is identical to array-based binary search: a window [lo, hi] over the candidate range, a midpoint test, and a half discarded each time.

Duplicates, and the bisect module

The version of binary search shown so far returns an index where the target occurs, not necessarily the first one, when the array has duplicate values. Consider a sorted list of exam scores with repeats: [61, 64, 64, 64, 70, 72, 72, 85, 90], and suppose you need the first index at which 64 occurs (index 1), or the index just past the last occurrence (index 4), to count how many students scored exactly 64. The basic algorithm above does not guarantee which of the three 64s it lands on; it depends on how the midpoints happen to fall.

Python's standard library exposes exactly the two variants needed for this: bisect.bisect_left, which returns the first position at which the target could be inserted while keeping the array sorted (equivalently, the first index of the target if present), and bisect.bisect_right, which returns the position just after the last occurrence.

import bisect

scores = [61, 64, 64, 64, 70, 72, 72, 85, 90]
first = bisect.bisect_left(scores, 64)
last_plus_one = bisect.bisect_right(scores, 64)
count = last_plus_one - first
print(first, last_plus_one, count)

This prints 1 4 3: the first 64 is at index 1, the slice of 64s ends just before index 4, and there are three of them. Both bisect_left and bisect_right are themselves binary searches internally, O(log n), so counting occurrences of a value in a sorted array this way is far cheaper than scanning and counting by hand.

Active recall

Attempt each question before reading its answer.

1. Trace binary search on arr = [2, 4, 6, 8, 10, 12, 14] (indices 0 to 6) searching for target 10. List lo, hi, mid, and the comparison result at every step, and state the final index and comparison count.
2. An array has 50,000 sorted elements. What is the worst-case number of comparisons binary search needs? Show the power-of-two bound you used.
3. The results portal from the opening of this chapter grows from 21,00,000 roll numbers to 42,00,000 (it doubles). By how much does the worst-case comparison count increase? Give the exact new value, not just "more."
4. A teacher has an unsorted list of 500 student names and needs to check whether one specific name is present, just this once. Should she sort the list and binary search it, or scan it directly? Justify with an approximate comparison count for each option.
5. An array [3, 3, 3, 3, 3] is searched for target 3 using the plain binary_search function from this chapter. What index does it return, and why might that be a problem if the task were "find the first index of 3"? What would you use instead?
6. What is the space complexity of the recursive binary search shown in this chapter, and why does the iterative version not share that cost?

Answers

1. Step 1: lo=0, hi=6, mid=3, arr[3]=8 < 10, so lo=4. Step 2: lo=4, hi=6, mid=5, arr[5]=12 > 10, so hi=4. Step 3: lo=4, hi=4, mid=4, arr[4]=10 == 10, match. Final index 4, found in 3 comparisons.
2. The smallest k with 2^k >= 50,000 is k=16, since 2^15 = 32,768 is below 50,000 and 2^16 = 65,536 clears it. So the worst case is 16 comparisons.
3. Doubling n adds exactly 1 to ceil(log2 n), since log2(2n) = log2(n) + 1. Checking directly: 2^22 = 41,94,304 is just under 42,00,000 and 2^23 = 83,88,608 clears it, so the new worst case is ceil(log2(42,00,000)) = 23, exactly one more than the 22 comparisons needed at 21,00,000. This is the ripple: the search cost barely reacts to a doubled dataset, even though the dataset itself is twice the size.
4. Scan it directly. A linear scan of 500 unsorted names costs at most 500 comparisons. Sorting first costs on the order of 500 * log2(500) ≈ 500 * 8.97 ≈ 4,485 comparisons before a single search can even begin, then a further ceil(log2 500) = 9 to binary search it, for roughly 4,494 total. That is about nine times more expensive than just scanning once, because the one-time sorting cost is never recovered when there is only one query to amortize it over.
5. The plain function can return any of indices 0 through 4, depending on where the midpoints fall (with lo=0, hi=4, the first midpoint is index 2, which already satisfies arr[2] == 3, so it returns 2 immediately). That is a problem if the task specifically needs the first occurrence, since index 2 is not the first index of 3. The fix is bisect.bisect_left(arr, 3), which is guaranteed to return the leftmost valid position, index 0 here.
6. O(log n), because the recursive version pushes one new stack frame for each recursive call, and the number of calls before the base case is reached equals the number of halvings, which is ceil(log2 n). The iterative version reuses the same three variables (lo, hi, mid) on every pass through the loop rather than growing a call stack, so its space usage stays O(1) regardless of how large the array is.

Think About It

Think about this: How would you explain binary search: finding a needle in a haystack to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind binary search: finding a needle in a haystack, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.