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 it is 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.

Run the rule once on real values before trusting the formula. Take the sorted array [2, 5, 8, 12, 16, 23, 38] (so n = 7) and search for 23:

lo=0, hi=6  →  mid=3, arr[3]=12 < 23  →  lo = mid+1 = 4   (indices 0–3 discarded)
lo=4, hi=6  →  mid=5, arr[5]=23 = 23  →  found at index 5

Two comparisons, and the second one threw away four of the seven candidates in a single stroke.

The worst case for n = 7 is three comparisons — hunting a value that is not in the array at all — which is ⌈log₂(7+1)⌉ = 3.

Counting comparisons

One word needs pinning down before any of this counting means anything. It is exactly where two students’ totals disagree: a “comparison” here means one probe of the middle element — the single three-way test “is the target equal to, less than, or greater than arr[mid]?”.

The Python below spends two if statements on that one probe, and GATE still counts it as one. “One comparison per level” is a claim about levels of the recurrence, not about lines of code.

The recurrence behind the count

With that fixed, 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