Skip to content
Tech Interview Prep
Technical interview guide

Binary Search

Halving the search space on sorted data, and the many variants beyond a plain lookup.

Read
40 min
Practice MCQs
25
Interview Q&A
25
Edition
v6
Editorial status
Reviewed

Scope: Language-neutral, with library behaviour cited from CPython 3.14 bisect, the C++ standard algorithms, and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-3A `first_at_least(a, x)` helper is used to splice a new record into a sorted index; it must return the index of the first element of `a` that is >= x, or `len(a)` if every element is smaller. The implementation is: ```python def first_at_least(a, x): lo, hi = 0, len(a) # hi is exclusive while lo < hi: mid = (lo + hi) // 2 if a[mid] < x: lo = mid + 1 else: hi = mid return lo ``` The call `first_at_least([1, 3, 5, 5, 5, 8, 9], 5)` is made. What does it return?
MCQ-1A service uses this lower_bound to find the first index with a[i] >= target in a sorted array of 10^9 ints: `lo, hi = 0, len(a)`; `while lo < hi: mid = lo + (hi - lo) // 2; if a[mid] < target: lo = mid + 1 else: hi = mid`; `return lo`. A teammate changes the else branch to `hi = mid - 1` to 'shrink faster'. On `a = [1, 3, 3, 3, 5, 7]` with `target = 3`, what does the modified loop return?
MCQ-23In a service that stores event IDs in a sorted array, this shipped routine returns the insertion index for a new ID: the index of the first stored ID >= t, or n when every stored ID is smaller than t. ```python def lower_bound(a, t): lo, hi = 0, len(a) - 1 while lo < hi: mid = (lo + hi) // 2 if a[mid] < t: lo = mid + 1 else: hi = mid return lo ``` The suite has 200 green tests against a 4096-element array, and every query value is an ID already stored in that array. Production reports wrong insertion indices. The team wants to add small hand-written cases: which single assertion would have failed on this shipped code and still pass against a correct lower_bound of the same signature?
MCQ-6A service keeps a sorted array of event timestamps, rebuilt from a stream on every request, and runs of identical timestamps can span millions of entries. A caller needs the index of the first occurrence of a target so it can slice the whole run; the current plain binary search returns an index in the middle of the run, so the slice starts mid-run. Which change makes the returned index the first occurrence?
MCQ-24An observability service keeps `samples`, a list of 2,000,000 ints sorted ascending with many duplicate timestamps. To find the first sample at or after a cutoff `t`, it runs a hand-written binary search that returns any index whose value equals `t`, or `-1` when `t` is absent. Window boundaries computed from that index drift by up to a few hundred samples whenever the cutoff lands on a duplicated timestamp. Which change removes the drift?
MCQ-7A latency histogram keeps its samples in a sorted list `lat = [5, 9, 9, 9, 14, 21, 21, 30]` (ms). To fill two adjacent buckets the code needs the number of samples strictly below 21 ms and the number at or below 21 ms, in that order. Which pair of calls returns those two counts?
MCQ-15An on-call engineer has `records`, a list of 8 dicts sorted by `name` ascending, each holding a `name` and an `age`: | index | name | age | |---|---|---| | 0 | alice | 45 | | 1 | bob | 22 | | 2 | carol | 61 | | 3 | dave | 30 | | 4 | erin | 55 | | 5 | frank | 18 | | 6 | grace | 40 | | 7 | heidi | 70 | They call `bisect_left(records, 30, key=lambda r: r["age"])` (Python 3.10+) to find the record with age 30. The call returns without raising. What is the result, and what does it mean?
MCQ-8A sorted array of n doubles holds many copies of a target value k. A query must return the exact number of elements equal to k in O(log n) worst-case time, using O(1) extra space and no preprocessing. Which procedure does this?
MCQ-4A Java service binary-searches a sorted `int[]` that can hold up to 2^30 + 1 elements. The midpoint line is `int mid = (lo + hi) / 2;`. Which statement about that line is accurate?
MCQ-5A teammate's binary search computes `mid = lo + (hi - lo) // 2` over an inclusive range and, in the branch that should raise the lower bound, assigns `lo = mid`. They argue the loop must finish because the range is finite. Which one-line summary of termination is right?
MCQ-21A service binary-searches a sorted array of 4,096 keys, and its loop runs at most 12 iterations in the worst case. The array is replaced by one of 1,048,576 keys, 256 times larger, with the same implementation and one key comparison per iteration. How many more iterations does the worst case need?
MCQ-2A team binary-searches for the smallest integer x in [1, 16] such that the monotone predicate x^2 >= 100 holds. Their loop is `lo, hi = 1, 16; while lo < hi: mid = lo + (hi - lo) // 2; if mid * mid >= 100: hi = mid - 1 else: lo = mid + 1; return lo`. What does the loop return?
MCQ-12A team binary-searches the smallest cache size C (integer MB, range [1, 16]) at which a workload's simulated hit rate reaches 90%. The simulator reports hit rates: C=1:50%, 2:70%, 3:92%, 4:88%, 5:85%, 6:91%, 7:89%, 8:95%, 9:93%, 10:90%, 11:94%, 12:96%, 13:92%, 14:97%, 15:95%, 16:98%. They run the standard 'find first true' loop: lo=1, hi=16; while lo<hi: mid=(lo+hi)//2; if hit(mid)>=90 then hi=mid else lo=mid+1; return lo. Which statement is correct?
MCQ-13When binary searching for the minimum valid capacity in contiguous partitioning problems (such as Capacity to Ship Packages or Painter's Partition), how should the search bounds [low, high] be initialized?
MCQ-25A courier ships ten packages in a fixed order, with weights 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 kg. Each day one truck makes a single trip carrying a contiguous run of the remaining packages, and every truck has the same capacity C kg. The courier has exactly 4 days. What is the smallest C that ships all ten packages in 4 days?
MCQ-14A pricing service binary-searches a model's breakeven price over [0.0, 1e9] to an absolute tolerance of 1e-12. In Python 3 with IEEE-754 doubles, the loop is: while hi - lo > 1e-12, set mid = (lo + hi) / 2, then hi = mid if cost(mid) >= 0 else lo = mid. The job never returns; the bounds have stopped moving at lo = 599999999.99999988079071044921875 and hi = 600000000.0, and every pass evaluates cost(600000000.0). Which change is correct?
MCQ-11You are implementing findMin on an array of distinct integers that is a rotation of a sorted array by an unknown offset in [0, n-1] (offset 0 means the array is already sorted). Using a search interval [low, high], which comparison rule correctly decides which half to discard?
MCQ-10When searching for a target value in a rotated sorted array that permits duplicate values, which structural condition causes the search complexity to degrade from O(log n) to O(n) in the worst case?
MCQ-9Here is the standard midpoint-vs-endpoint search for a target in a rotated sorted array: ```python def search(a, target): lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] == target: return mid if a[lo] <= a[mid]: # left half sorted if a[lo] <= target < a[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half sorted if a[mid] < target <= a[hi]: lo = mid + 1 else: hi = mid - 1 return -1 ``` A caller runs `search([1, 3, 1, 1, 1], 3)`. What does it return, and why?
MCQ-19A read-only 4096 × 4096 grid has every row sorted ascending and every column sorted ascending. The lookup routine flattens the grid row-major into a 16,777,216-element array and binary searches it, so a miss costs 24 comparisons. It returns 'not found' for some targets that are present. Which change fixes the lookup and keeps the worst case under 10,000 comparisons?
MCQ-20Two sorted arrays, A = [1, 4, 9, 12] and B = [2, 3, 5, 8, 10], are searched for their median with the partition method, which binary-searches the split point of the shorter array A. At the current probe the split of A is i = 3, so the largest element on A's left is 9 and the smallest element on B's right is 5. What does the algorithm do next?
MCQ-16A batch job loads a fixed array of 1,000,000 random ints and answers exactly 10 membership queries before exiting. The job may not allocate any auxiliary data structure. Which plan answers all 10 queries correctly with the least comparison work?
MCQ-17A service keeps 10 million 64-bit IDs in memory and takes 200,000 queries per second: 96% are "is ID x present?" and 4% are "what is the smallest ID ≥ x?". Today the IDs sit in a sorted array, where a point lookup costs about 250 ns (20 binary-search steps) and an ordered query about 250 ns. A teammate proposes swapping it for a hash set, where a point lookup costs 80 ns but an ordered query must scan all 10M entries, about 40 ms. Memory is not the constraint. What should the design doc say?
MCQ-18An in-memory index holds 2^24 = 16,777,216 sorted 8-byte keys in one contiguous array, 128 MB total. A binary search runs 24 probes, each a dependent load; DRAM latency is ~80 ns and an L1 hit ~1 ns. Which estimate of the lookup's p99 does the access pattern predict?
MCQ-22A service exposes a sorted sequence of 2^20 timestamps only through `value_at(i)`, which costs one 40 ms network round trip per call. A migration checklist proposes binary search over this implicit array to find a target timestamp. What does the search cost?