Top 5 Binary search Interview Questions
Browse 5 real-world technical and behavioral interview questions about Binary search. Review scenarios, edge cases, and architectural best practices.
Find the rotation point of a rotated sorted array, then do it again when the array has duplicates.
Binary search for the rotation point by comparing the middle element with the right end. If it is larger, the break lies to the right; otherwise it is at mid or before it. That is O(log n). With duplicates an equal comparison says nothing, so you drop the right end, and the worst case becomes O(n).
Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?
Russian doll envelopes reduce to a longest increasing subsequence. Sort by width ascending, break width ties by height descending, then run the O(n log n) tails search on heights. The descending tie-break stops equal widths from chaining, since a strictly increasing run then takes at most one per width.
Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D days
When you cannot construct the answer but can cheaply test a candidate, and that test is monotone, binary search the answer's numeric range instead of the input. The feasibility check here is greedy day-packing, giving O(n log S) time, and the whole implementation hinges on one loop invariant. It also connects monotonicity to the point an interviewer is testing.
Find the length of the longest strictly increasing subsequence, then get it under quadratic time.
The quadratic dynamic programme asks for the best chain ending at each index. The faster version keeps one array where slot j holds the smallest possible tail of an increasing subsequence of length j plus one; that array stays sorted, so each element is placed by binary search for O of n log n.
You are given a sorted array that has been rotated by an unknown amount. Find a target value in logarithmic time.
Search a rotated sorted array in O(log n) by finding which half is sorted at each midpoint, then keeping the half where the target can legally fall. With duplicates, equal endpoints can hide the pivot, so the worst case becomes linear.