Linear & Binary Search
Scan left-to-right in O(n), or halve a sorted range in O(log n) — and count the comparisons the way GATE does.
What you'll learn
- Linear search scans left-to-right: O(n) worst, O(1) best, and needs no sorting
- Binary search requires a sorted array and halves the range each comparison: O(log n)
- Worst-case comparisons obey F(n) = F(floor(n/2)) + 1, about ceil(log2(n+1))
- Why the comparison count is the recurrence's depth, not the sum of both halves
Before you start
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 is left or right, and throw away half the array in a single comparison. 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.
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 not.
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.
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 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.
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
nelements, write the recurrence for the maximum number of comparisons, then evaluate it forn = 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 = 10So 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.
Quick check
Quick check
Practice this in an interview
All questionsBinary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.
Even after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.
A B-tree index stores key values in a balanced tree of sorted nodes, allowing the engine to reach any value in O(log n) page reads instead of scanning every row. The optimizer skips the index when the estimated cost of random I/O exceeds a full-table scan, when a function wraps the indexed column, or when the query returns such a large fraction of rows that a sequential scan is cheaper.