Linear & Binary Search

The last lesson kept naming binary search as the hero of O(log n) — the halving that turns a million items into twenty comparisons. Now meet it properly, alongside its plodding cousin. Finding an item in a list has two textbook strategies, and the gap between them is the whole lesson. Linear search is the brute-force one: start at the left and check each element until you hit the target or fall off the end. Binary search is the clever one: if the array is already sorted, jump to the middle, decide whether the target lies left or right, and throw away half the array in a single comparison. Then repeat. The first is patient; the second is ruthless.

That “throw away half each time” is why binary search scales: one million sorted items need only about twenty comparisons, while a linear scan could need all million. The price of that speed — as we will see — is the one demand the last lesson hinted at.

Linear search — the baseline

Walk the array from index 0 rightward. The best case is a hit on the first element (O(1)); the worst case is the target sitting last or absent, forcing n comparisons (O(n)). Crucially, linear search needs no ordering — it works on any list, sorted or jumbled. That freedom is the trade: it asks nothing of the data, and in return it can promise nothing better than O(n).

Binary search — halving a sorted range

Keep two bounds, lo and hi, around the live range. Look at the middle element. If it equals the target you are done; if the target is larger, discard the left half (lo = mid + 1); if smaller, discard the right half (hi = mid - 1). Each comparison cuts the candidate count roughly in half — and that single act of discarding is the whole secret.

Step through it and watch the comparison counter: the live range collapses n → n/2 → n/4 → … until one element (or none) remains. The number of halvings to get there is exactly what O(log n) measures.

The worst-case comparison count satisfies a one-line recurrence: solve a problem of size n with one comparison plus a subproblem of half the size.

Here is the algorithm in full, with a comparison counter, beside the recurrence computed directly — so you can see the two agree:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    comparisons = 0
    while lo <= hi:                 # note: lo <= hi, not lo < hi
        comparisons += 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid, comparisons
        elif arr[mid] < target:
            lo = mid + 1            # discard the left half
        else:
            hi = mid - 1            # discard the right half
    return -1, comparisons

# Worst-case comparisons via the recurrence F(n) = F(n//2) + 1
def F(n):
    return 0 if n == 0 else F(n // 2) + 1

print("F(1000) =", F(1000))
print("F(1024) =", F(1024))
print("F(1000000) =", F(1000000))

arr = list(range(1000))            # sorted 0..999
_, c = binary_search(arr, 10_000)  # absent target → worst case
print("comparisons to fail on n=1000:", c)

prints:

F(1000) = 10
F(1024) = 11
F(1000000) = 20
comparisons to fail on n=1000: 10

The empirical worst-case count (10 for n = 1000) matches the recurrence F(1000) = 10 exactly — the recurrence is not a guess, it is the algorithm’s depth.

How GATE asks this

The 2024 paper posed it as a NAT/MCQ on the recurrence itself: which relation gives the maximum number of comparisons binary search makes on n elements? The correct answer was option A, F(n) = F(⌊n/2⌋) + 1 — not the tempting F(⌊n/2⌋) + F(⌈n/2⌉). Binary search recurses into only one half, so you add a single comparison per level; you never explore both halves. The other classic form is a plain NAT: “max comparisons to search a sorted array of n items?”, answered with ⌈log₂(n+1)⌉ (equivalently ⌊log₂ n⌋ + 1).

Worked example — the 2024 recurrence

For binary search on a sorted array of n elements, write the recurrence for the maximum number of comparisons, then evaluate it for n = 1000.

The array of n costs one comparison at the middle, after which at most one half survives — a subproblem of size ⌊n/2⌋:

F(n) = F(⌊n/2⌋) + 1,   F(0) = 0

F(1000) = F(500) + 1
        = F(250) + 2
        = F(125) + 3
        = F(62)  + 4
        = F(31)  + 5
        = F(15)  + 6
        = F(7)   + 7
        = F(3)   + 8
        = F(1)   + 9
        = F(0)   + 10  =  10

So 10 comparisons, matching ⌈log₂(1000+1)⌉ = 10. A sorted array of exactly 1024 elements halves 1024 → 512 → 256 → … → 1 in ten steps — log₂(1024) = 10 — so binary search settles it in roughly ten comparisons too, against up to 1024 for a linear scan.

A question to carry forward

Binary search’s logarithmic speed comes with a non-negotiable price of admission, stated plainly in trap (1): the data must already be sorted. Linear search asks nothing of its input and pays O(n); binary search asks for order and is rewarded with O(log n). Which raises the obvious next question — where does that sorted array come from in the first place? Here is the thread onward: what are the simplest algorithms that take a jumbled list and put it in order, how do you trace them pass by pass, and what do they cost?

In one breath

• Linear search: scan left-to-right; needs no ordering; best O(1), worst/average O(n).
• Binary search: needs a sorted array; halve the live range each comparison → O(log n).
• Worst-case comparisons obey F(n) = F(⌊n/2⌋) + 1 (one half, one comparison) ≈ ⌈log₂(n+1)⌉ — not F(⌊n/2⌋) + F(⌈n/2⌉).
• Concretely: n = 1000 → 10, n = 10⁶ → 20, n = 15 → 4 comparisons.
• Traps: sorted-only, add 1 (don’t sum halves), loop condition lo <= hi.

Practice