Searching and binary search

In short

Searching means locating a key in a collection, or proving it is absent. Linear search works on any sequence in O(n); binary search exploits order to halve the search space each step and finishes in O(log n) — 30 probes for a billion sorted records instead of a billion. It is examined in every Indian university DAA/Data Structures paper and sits under "Searching, sorting, hashing" in the GATE CSE syllabus (recurrence, comparison counts, decision-tree lower bound). In placements it is the single most reused primitive: TCS NQT, Infosys, Wipro and Capgemini ask the plain version and the off-by-one traps; Amazon, Google, Microsoft, Flipkart, Zoho, Zomato, Swiggy, Walmart Global Tech and PhonePe ask "binary search on the answer" problems almost every round.

Explained

The search problem and linear search

• Input: a collection of n records, a key k, and an equality (and for binary search, an ordering) on keys. Output: position of k, or "not present".
• Internal vs external search: data in RAM (array, tree, hash table) versus on disk (B-tree/B+-tree index), where the cost unit is a *disk block read*, not a comparison.
• Static vs dynamic: a static sorted array suits binary search; frequent inserts/deletes favour a BST, skip list or hash table, since maintaining a sorted array costs O(n) per insert.
• Linear (sequential) search: scan left to right. Works on unsorted data, linked lists and streams; O(n) time, O(1) space. Worst case n comparisons; average (n+1)/2 for a successful search with uniform key distribution, n for an unsuccessful one.
• Sentinel linear search: place the key at the end so the loop needs only one test per step instead of two — same O(n), a constant-factor win sometimes asked in vivas.
• Linear search beats binary search for small n (roughly n ≤ 20-60 in practice) because of cache-friendly sequential access and no branch misprediction; CPU cache effects are why real libraries switch to linear scan in small ranges.

Binary search: idea, invariant and correctness

• Precondition: elements are sorted (ascending, say) and randomly accessible in O(1) — so arrays yes, linked lists effectively no (traversal makes it O(n)).
• Method: compare k with the middle element; if equal, done; if k is smaller, discard the middle and everything right of it; else discard the middle and everything left. Repeat on the surviving half.
• Loop invariant: "if k is present, it lies in a[lo..hi]". Initially true (lo=0, hi=n−1); each step preserves it because the discarded half cannot contain k by ordering; the loop ends when the range is empty (absent) or the middle equals k (present) — this is the standard exam proof of correctness.
• Termination: the range length strictly decreases (hi−lo+1 → at most ⌈(hi−lo)/2⌉), so the loop runs at most ⌈log₂(n+1)⌉ times.
• Three-way version (compare once, test <, =, >) finds an existing key in at most ⌊log₂ n⌋+1 comparisons. Two-way version (single < test, exit only when the range is empty) always runs ⌈log₂(n+1)⌉ iterations but has one cheap comparison per step — usually faster on modern hardware.
• Space: O(1) iterative; the recursive form is tail-recursive but still O(log n) stack frames unless the compiler eliminates them.

Writing it without bugs (the part interviews test)

• Overflow: mid = (lo + hi) / 2 overflows 32-bit int in C/C++/Java when lo+hi > 2³¹−1 (≈2.15×10⁹) — the famous bug in Java's Arrays.binarySearch fixed in 2006. Use mid = lo + (hi − lo) / 2, or (lo + hi) >>> 1 in Java. Python's ints are arbitrary precision, so the bug cannot occur there.
• Two safe templates, and the matching mid: with hi = mid (half-open, answer kept in the range) use the *lower* mid lo + (hi−lo)/2; with lo = mid use the *upper* mid lo + (hi−lo+1)/2. Mixing them gives an infinite loop when hi = lo+1.
• Prefer the predicate form: define a boolean that is monotone over the range (false…false, true…true) and search for the first true. Every variant below is then the same five lines with a different predicate.
• lower_bound(k): first index with a[i] ≥ k. upper_bound(k): first index with a[i] > k. Together they give the first occurrence, the last occurrence (upper_bound−1), the count of k (upper_bound − lower_bound) and the insertion position — so duplicates need no special code.

// first index i with a[i] >= k, else n  (lower_bound)
int lower(const vector<int>& a, int k){
    int lo = 0, hi = a.size();              // half-open [lo, hi)
    while (lo < hi){
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < k) lo = mid + 1; else hi = mid;
    }
    return lo;                               // == n means k is larger than all
}
// classic search
int bsearch(const vector<int>& a, int k){
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi){
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == k) return mid;
        if (a[mid] < k) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

• Library equivalents: C++ binary_search, lower_bound, upper_bound, equal_range; Java Arrays.binarySearch (returns −(insertion point)−1 when absent) and Collections.binarySearch; Python bisect.bisect_left, bisect.bisect_right, bisect.insort.

Complexity, derivation and the lower bound

• Recurrence: T(n) = T(n/2) + Θ(1), T(1) = Θ(1). Unrolling: after i steps the range is n/2ⁱ; it empties when 2ⁱ > n, i.e. i = ⌈log₂(n+1)⌉ → T(n) = Θ(log n).
• Master theorem: a = 1, b = 2, f(n) = Θ(1); n^{log_b a} = n⁰ = 1 = f(n) → case 2 → Θ(n⁰ log n) = Θ(log n).
• Average successful comparisons ≈ log₂ n − 1 for large n (from the internal path length of the complete comparison tree); the average is only about one probe cheaper than the worst case, because most nodes sit in the bottom level.
• Decision-tree lower bound: any comparison-based search is a decision tree distinguishing 2n+1 outcomes (n hits and n+1 "gaps"); its n internal nodes force a height ≥ ⌊log₂ n⌋, so the worst case is ≥ ⌈log₂(n+1)⌉ comparisons − binary search is optimal among comparison-based methods. Beating log n requires extra assumptions (hashing, key structure, uniform distribution).
• Including the sort: if the array is unsorted, sorting costs Θ(n log n). For k searches, sort+binary ≈ n log₂n + k log₂n versus linear k·n/2 — break-even is roughly k ≈ 2 log₂ n searches (about 40 searches at n = 10⁶). One-off search on unsorted data: just scan.
• Ternary search on a sorted array is worse: it uses about 2·log₃ n ≈ 1.26·log₂ n comparisons. Ternary search is for unimodal functions (maximise/minimise), not for sorted lookup.

Variants and relatives

• First / last occurrence, count, floor and ceiling of a key — all lower_bound/upper_bound applications.
• Rotated sorted array (no duplicates): compare a[mid] with a[lo] (or a[hi]) to decide which half is sorted, then test whether k lies inside it — O(log n). With duplicates, the worst case degrades to O(n) (e.g. 2 2 2 2 3 2 2).
• Unknown / infinite size (exponential or galloping search): probe indices 1, 2, 4, 8, … until a[i] > k, then binary search in [i/2, i] — O(log p) where p is the answer's position.
• Peak element in an array with no two equal neighbours: if a[mid] < a[mid+1] a peak lies right, else left — O(log n) although the array is not sorted (the *predicate* is monotone, not the data).
• 2D matrices: fully row-major sorted m×n matrix → treat as one array of length mn, O(log mn). Rows sorted left-to-right *and* columns top-to-bottom → staircase search from the top-right corner, O(m+n).
• Binary search on the answer (parametric search): when checking "is answer X feasible?" is easy and feasibility is monotone in X, binary search the answer range. Covers allocate-minimum-pages, painter's partition, split array largest sum, aggressive cows, capacity to ship packages, minimum days, "Koko eating bananas", kth smallest in a multiplication table, and median of two sorted arrays.
• Real-valued binary search: bisect on [lo, hi] for a fixed iteration count or until hi−lo < ε — used for √x, cube roots, and geometry/optimisation problems.
• Jump (block) search: step √n ahead, then scan back — O(√n), useful when jumping backwards is costly, since it steps back only once (binary search may jump back O(log n) times).
• Interpolation search: guesses the position proportionally; O(log log n) average on uniformly distributed sorted keys but O(n) worst case. Fibonacci search: splits by Fibonacci numbers, uses only addition/subtraction — historically for machines without division.
• Non-comparison alternatives: hash table O(1) average but O(n) worst and no order queries; BST/AVL/Red-Black O(log n) with dynamic updates; B-tree / B+-tree O(log_B n) *disk reads* — this is what a MySQL/PostgreSQL index on an Aadhaar-style unique column actually does; trie for string prefixes.

Key points

• Precondition - binary search needs sorted data and O(1) random access; on a linked list it is pointless.
• Halving - each step discards at least half the remaining elements, so at most ⌈log₂(n+1)⌉ probes.
• Worst case (3-way) - ⌊log₂ n⌋ + 1 comparisons for a hit; unsuccessful search always costs the full ⌈log₂(n+1)⌉.
• Recurrence - T(n) = T(n/2) + O(1) → Θ(log n) time, O(1) iterative space, O(log n) recursive stack.
• Optimality - the decision-tree bound ⌈log₂(n+1)⌉ proves no comparison-based search can do better.
• mid overflow - always lo + (hi − lo)/2, never (lo + hi)/2 in C++/Java.
• Invariant - "if present, k is in a[lo..hi]"; the proof in exams is invariant + strictly shrinking range.
• lower_bound / upper_bound - first ≥ k and first > k; their difference is the count of k.
• Duplicates - plain binary search returns *any* occurrence; use bounds when you need the first or last.
• Monotone predicate - binary search needs monotonicity of a predicate, not sortedness of data (peak element, rotated array).
• Binary search on answer - search the value range when feasibility is monotone and checkable in O(n); total O(n log(range)).
• Linear search - O(n), works unsorted, on streams and lists; faster than binary for very small n.
• Sorting first - costs Θ(n log n); worth it only for repeated searches (break-even ≈ 2 log₂ n queries).
• Ternary search - for unimodal optimisation, not for sorted lookup (1.26× more comparisons than binary).
• Interpolation search - O(log log n) average on uniform keys, O(n) worst.
• Rotated array with duplicates - degrades to O(n) in the worst case.
• External search - B+-tree indexes minimise disk block reads: O(log_B n), the database equivalent of binary search.
• Real-valued bisection - iterations = ⌈log₂((hi − lo)/ε)⌉; prefer a fixed 100 iterations to avoid float loops that never end.

Formulas and examples

(n = number of elements, k = search key, lo/hi = range bounds, ε = tolerance, m = block size; all times in comparisons or probes, which are dimensionless counts.)

Example 1 - trace on 15 sorted marks. a = [12, 18, 23, 29, 35, 41, 47, 52, 58, 63, 70, 77, 84, 91, 98], indices 0-14.

• Search k = 77: lo=0, hi=14 → mid=7, a[7]=52 < 77 → lo=8. mid=(8+14)/2=11, a[11]=77 → found at index 11 in 2 probes. Bound: ⌊log₂15⌋+1 = 3+1 = 4, so 2 ≤ 4 ✓.
• Search k = 60 (absent): mid=7 (52<60) → lo=8; mid=11 (77>60) → hi=10; mid=9 (63>60) → hi=8; mid=8 (58<60) → lo=9 > hi=8 → stop. 4 probes = ⌈log₂16⌉ = 4 ✓. Insertion position returned by lower_bound = 9.

Example 2 - scale of the saving. Comparisons in the worst case:

At 10⁸ comparisons/second, scanning 1 crore sorted records takes ≈ 0.1 s; binary search takes 24 comparisons ≈ 0.24 microseconds — about 4 lakh times fewer operations.

Example 3 - duplicates with bounds. a = [2, 4, 4, 4, 7, 9, 9, 11] (indices 0-7), k = 4.

• lower_bound(4): lo=0, hi=8 → mid=4 (a[4]=7 ≥ 4) → hi=4; mid=2 (a[2]=4 ≥ 4) → hi=2; mid=1 (a[1]=4 ≥ 4) → hi=1; mid=0 (a[0]=2 < 4) → lo=1 → 1.
• upper_bound(4) = lower_bound of first value > 4 → 4. So first occurrence = 1, last = 3, count = 4 − 1 = 3 ✓.

Example 4 - binary search on the answer (allocate minimum pages). Books with pages [12, 34, 67, 90] to be split among 2 students as contiguous blocks; minimise the maximum pages a student reads.

• Search range: lo = max = 90, hi = sum = 203. Predicate feasible(X) = "blocks of sum ≤ X need at most 2 students" (monotone: true for larger X).
• mid=146: 12+34+67=113, +90 = 203 > 146 → 2 students → feasible → answer ≤ 146, hi=145.
• mid=117: same split, 2 students → feasible → hi=116. mid=103: 12+34=46, +67=113 > 103 → cut (2nd student starts at 67), 67+90=157 > 103 → 3rd student → infeasible → lo=104.
• mid=110 → infeasible (3 students) → lo=111. mid=113: 12+34+67=113 ≤ 113, then 90 → exactly 2 students → feasible → hi=112. mid=111 → infeasible → lo=112; mid=112 → infeasible → lo=113 > hi=112.
• Answer = 113 pages ([12,34,67] and [90]). Cost: 7 feasibility checks × O(n) instead of exponential enumeration; generally O(n log(sum)).

Example 5 - √10 by bisection. lo=0, hi=10, ε = 10⁻³ → iterations needed = ⌈log₂(10/0.001)⌉ = ⌈log₂10000⌉ = ⌈13.29⌉ = 14.

• mid=5 → 25 > 10 → hi=5; mid=2.5 → 6.25 < 10 → lo=2.5; mid=3.75 → 14.0625 > 10 → hi=3.75; mid=3.125 → 9.7656 < 10 → lo=3.125; mid=3.4375 → 11.816 > 10 → hi=3.4375; mid=3.28125 → 10.767 > 10 → hi=3.28125; mid=3.203125 → 10.260 > 10 → hi=3.203125. Range is now [3.125, 3.203] and converges to 3.16228 (√10 = 3.16228 to 5 decimals).

Where it is used

• Databases and backends: B+-tree indexes in MySQL/PostgreSQL behind every indexed lookup — IRCTC PNR and train-availability queries, UIDAI/Aadhaar-scale key lookups, GSTN return searches; EXPLAIN showing "index seek" instead of "full table scan" is this idea in production.
• E-commerce and fintech: price/rating range filters and leaderboard ranks on Flipkart, Myntra and Nykaa; order-book price-level lookup and matching at Zerodha, Groww and NSE/BSE systems; rate-limit and bucket boundary lookups at PhonePe/Razorpay.
• Systems and infrastructure: git bisect to find a breaking commit, binary searching a config/threshold during capacity planning, LSM-tree sparse-index probes in Cassandra/RocksDB, timestamp lookup in time-series and log stores.
• Maps, logistics and ML: nearest-timestamp GPS interpolation and ETA tables at Ola, Uber, Delhivery and Zomato; quantile/threshold search and learning-rate or cutoff tuning in model deployment.
• Job roles: SDE and backend developer interviews (DSA rounds), database and performance engineers, quant/HFT developers, competitive programming (CodeChef, Codeforces, ICPC) where "binary search the answer" is a standard tool.
• Exams and recruitment tests: GATE CSE/DA questions on comparison counts and recurrences; TCS NQT, Infosys HackWithInfy, Wipro NTH, Accenture and Capgemini coding sections; PSU and ISRO/DRDO CS papers.

Interview questions

• Q: What is the time complexity of binary search and how is it derived? A: Θ(log n), from T(n) = T(n/2) + O(1); the range shrinks by half each step, so it empties after ⌈log₂(n+1)⌉ steps (Master theorem case 2 gives the same).
• Q: Can binary search be applied to a linked list? A: Logically yes, but reaching the middle costs O(n) traversal, so the total becomes O(n) — worse than a plain scan; skip lists exist to give list-like structures O(log n) search.
• Q: Why is mid = (lo + hi)/2 considered a bug? A: lo + hi can overflow a 32-bit signed int for large arrays, giving a negative index; lo + (hi − lo)/2 cannot overflow.
• Q: How do you find the first and last occurrence of a repeated key? A: Use lower_bound (first index with a[i] ≥ k) and upper_bound (first with a[i] > k); the last occurrence is upper_bound − 1 and the count is their difference.
• Q: Binary search needs sorted data, yet "find a peak element" works in O(log n) on unsorted data. Why? A: What binary search really needs is a monotone predicate; comparing a[mid] with a[mid+1] always tells you a side that must contain a peak, which is enough to halve the range.
• Q: How do you search in a rotated sorted array? A: Find which half of [lo, mid, hi] is sorted by comparing a[mid] with a[lo]; if the key lies within that sorted half's range, search there, else search the other half — O(log n), degrading to O(n) with many duplicates.
• Q: Is binary search the best possible search? A: Yes among comparison-based methods — the decision tree must have ≥ n+1 leaves, so ≥ ⌈log₂(n+1)⌉ comparisons in the worst case; hashing beats it only by abandoning comparisons and order queries.
• Q: When would you prefer linear search? A: Unsorted or streaming data, linked structures, a single query on an unsorted array, or very small n where cache locality makes the scan faster.
• Q: Explain "binary search on the answer" with an example. A: If feasibility is monotone in the answer, bisect the answer range and test feasibility: e.g. minimise the maximum pages per student by testing "can the books be split within X pages?" in O(n) per test, giving O(n log(sum)).
• Q: How many iterations for a real-valued binary search to 10⁻⁶ precision on [0, 10⁹]? A: ⌈log₂(10⁹/10⁻⁶)⌉ = ⌈log₂10¹⁵⌉ ≈ 50 — in practice people just run a fixed 100 iterations.
• Q: What does Java's Arrays.binarySearch return when the key is absent? A: −(insertion point) − 1, so a negative value both signals absence and encodes where the key would go.
• Q: Why does interpolation search not replace binary search? A: Its O(log log n) advantage assumes nearly uniform key distribution; on skewed data it degenerates to O(n), while binary search stays O(log n) regardless.

Common mistakes

• Using (lo + hi)/2 and ignoring integer overflow, or using hi = mid with the lower mid plus lo = mid elsewhere — producing an infinite loop when hi = lo + 1.
• Off-by-one in the bounds: mixing closed [lo, hi] with while (lo < hi), or hi = n with while (lo <= hi) — pick one convention and keep it.
• Forgetting the sortedness precondition — running binary search on unsorted input and getting a plausible but wrong answer in the lab.
• Reporting O(log n) for "sort then binary search" on unsorted data; the sort dominates at Θ(n log n).
• Assuming plain binary search returns the *first* occurrence when duplicates exist, then writing a linear backward scan that makes the worst case O(n) instead of using lower_bound.
• Confusing ternary search with binary search for sorted lookup, or applying ternary search to a non-unimodal function.
• Mis-stating comparison counts: ⌊log₂ n⌋ + 1 is the worst case for a hit, not the average, and an unsuccessful search does not stop early.
• In answer-space binary search, choosing wrong initial bounds (lo below the true minimum feasible value, or hi below the answer) or a predicate that is not actually monotone.

Related topics

Divide and conquer · Time and space complexity · Sorting algorithms · DSA interview patterns · Trees, BSTs and heaps · Hashing and hash tables