| Linear search | O(n) time, O(1) space — works on unsorted or sorted data |
| Binary search | O(log n) time, O(1) space (iterative) — requires sorted input |
| Ternary search | O(log₃ n) time — more comparisons per step than binary search |
| Jump search | O(√n) time, O(1) space — optimal block size is √n |
| Exponential search | O(log n) time — ideal for unbounded/infinite sorted streams |
| Interpolation search | O(log log n) average on uniform data, O(n) worst case |
| Arrays.binarySearch() | O(log n) — returns -(insertion point) - 1 when not found |
| Binary search on answer | O(log(range) × cost of feasibility check) |
Searching Algorithms & Binary Search Interview Questions & Answers
Q1. What is linear search and what is its time complexity?
A: Linear search scans a collection element by element, comparing each one to the target until a match is found or the collection is exhausted. It works on both sorted and unsorted data because it makes no assumptions about ordering. Its time complexity is O(n) in the worst and average case and O(1) in the best case (target is the first element), with O(1) extra space.
Q2. When would you choose linear search over binary search even though binary search is asymptotically faster?
A: Linear search is the right choice when the data isn't sorted and sorting it first would cost more than a single O(n) scan, or when the collection is small enough that constant-factor overhead dominates asymptotic gains. It's also necessary for data structures without random access, like singly linked lists, where jumping to an arbitrary middle index isn't O(1). Finally, if you only need one lookup ever, sorting purely to enable binary search is wasted O(n log n) work.
Q3. How would you implement linear search in Java, and what small optimization can reduce constant-factor overhead?
A: The straightforward version loops through the array comparing each element to the target and returns the index on a match. A classic micro-optimization is the "sentinel" trick: temporarily place the target at the last index so the loop never needs a separate bounds check, only a value check, though in modern JITs this rarely beats a well-optimized plain loop. Both variants remain O(n) asymptotically; the sentinel trick only reduces per-iteration constant work.
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}Q4. What is binary search and what precondition must the input satisfy?
A: Binary search finds a target in a sorted collection by repeatedly comparing it to the middle element and discarding the half that cannot contain it, narrowing the search range each step. The critical precondition is that the data must be sorted (or otherwise monotonic with respect to the comparison) — running binary search on unsorted data produces undefined, often wrong, results without any error. This halving strategy is what gives it O(log n) time instead of linear search's O(n).
Q5. What is the time and space complexity of an iterative binary search implementation?
A: Time complexity is O(log n) because each comparison eliminates half of the remaining search space, so at most log₂(n) comparisons are needed. Space complexity is O(1) for the iterative version since it only tracks a few integer pointers (low, mid, high) and never grows a call stack. This O(1) space is the main practical advantage of the iterative form over the recursive form.
int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Q6. What is the time and space complexity of a recursive binary search implementation?
A: Time complexity remains O(log n), identical to the iterative version, since the same halving logic applies. Space complexity, however, is O(log n) due to the recursion call stack — each recursive call adds a stack frame, and there are at most log₂(n) nested calls before the base case is hit. This makes the iterative form preferable in memory-constrained or extremely large-input contexts.
int binarySearchRec(int[] arr, int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
return arr[mid] < target
? binarySearchRec(arr, mid + 1, high, target)
: binarySearchRec(arr, low, mid - 1, target);
}Q7. Why is binary search's time complexity O(log n)?
A: Each comparison discards exactly half of the remaining candidates, so after k comparisons the search space shrinks from n to n/2ᵀ. The algorithm terminates when the space reaches size 1 (or 0), which happens when n/2ᵀ ≈ 1, i.e., k ≈ log₂(n). This logarithmic growth is why binary search scales so well — doubling the input size adds only one more comparison.
Q8. Why do experienced engineers write mid = low + (high - low) / 2 instead of mid = (low + high) / 2?
A: The naive form (low + high) / 2 can overflow a 32-bit int if low and high are both close to Integer.MAX_VALUE, since their sum exceeds the int range before the division happens, producing a negative or garbage mid index. The rewritten form low + (high - low) / 2 avoids this because high - low is bounded by the array length, which is far smaller than MAX_VALUE. This is a well-known real bug that famously affected early binary search implementations in production libraries.
// risky when low, high are both near Integer.MAX_VALUE:
int midUnsafe = (low + high) / 2; // may overflow and go negative
int midSafe = low + (high - low) / 2; // always safeQ9. What is the classic off-by-one bug of writing high = mid instead of high = mid - 1 after a non-match?
A: If the comparison determines the target is not at mid but could still be to the left, using high = mid keeps mid itself in the search range even though it was already ruled out, which can cause an infinite loop when low and high converge on that same index without progress. The correct move, once you've confirmed arr[mid] != target and the target is smaller, is high = mid - 1 to exclude mid entirely. This bug typically manifests as the loop hanging rather than returning a wrong answer, making it easy to spot in testing but easy to introduce under interview pressure.
Q10. What is the difference between using while (low <= high) versus while (low < high) as the loop condition?
A: low <= high is used for "find exact match" searches where the range can legitimately shrink to a single valid element (low == high) that still needs checking; the loop exits when low exceeds high, meaning nothing is left. low < high is used for "find a boundary" searches (like lower_bound or finding a minimum in a rotated array) where you deliberately converge low and high to the same index without evaluating it inside the loop, then return that index after the loop. Mixing up which template you're using is one of the most common sources of real bugs in binary search variants.
Q11. How do you avoid infinite loops in the low < high binary search template used for boundary-finding?
A: When narrowing toward a lower boundary, using mid = low + (high - low) / 2 (which rounds down) paired with high = mid is safe, but pairing a floor-rounded mid with low = mid can loop forever if low and high are adjacent (mid recomputes to low again). The fix is to round mid up in that case with mid = low + (high - low + 1) / 2 whenever the update is low = mid. Getting this rounding direction wrong is the single most common cause of infinite loops in "find boundary" binary search code.
Q12. What is the difference between binary search "on array indices" and binary search "on an answer/value space"?
A: Index-based binary search operates directly on a sorted array, narrowing low/high pointers that represent array positions, and typically looks for an exact stored value. Answer-space binary search instead searches over a range of possible answers (e.g., capacities, speeds, distances) where the array itself may be unsorted, using a monotonic feasibility check (can we succeed with this value?) instead of an equality comparison to decide which half to keep. Both rely on the same halving idea, but the second is a much more general problem-solving pattern once you recognize a monotonic yes/no function over a range.
Q13. How do you implement binary search on a sorted array that may contain duplicate values, returning any matching index?
A: The standard binary search algorithm works unchanged — duplicates don't break correctness for finding "some" index equal to the target, because as soon as arr[mid] == target you can return immediately. The only behavior difference from a duplicate-free array is that the returned index isn't guaranteed to be the first or last occurrence; which duplicate you land on depends on where mid happens to fall.
int findAny(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid; // could be any duplicate
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Q14. How do you find the first (leftmost) occurrence of a target in a sorted array with duplicates?
A: Run a modified binary search that, on finding a match, records the index but keeps searching the left half (high = mid - 1) instead of stopping, because an earlier occurrence might still exist. This preserves O(log n) time while guaranteeing the leftmost match is ultimately returned.
int firstOccurrence(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) { result = mid; high = mid - 1; }
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return result;
}Q15. How do you find the last (rightmost) occurrence of a target in a sorted array with duplicates?
A: This mirrors the first-occurrence search: on a match, record the index and keep searching the right half (low = mid + 1) instead of stopping, since a later occurrence could still exist. Combining first- and last-occurrence searches lets you compute the total count of the target as last - first + 1 in O(log n), instead of an O(n) linear count.
int lastOccurrence(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) { result = mid; low = mid + 1; }
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return result;
}Q16. How do you count the total occurrences of a target value in a sorted array using binary search?
A: Find the first occurrence index and the last occurrence index independently, each via a dedicated O(log n) binary search. If the first-occurrence search returns -1, the target isn't present at all, so the count is 0; otherwise the count is lastIndex - firstIndex + 1. This is O(log n) total, far better than an O(n) linear scan that tallies matches directly.
Q17. How do you find the "search insert position" — the index where a target should be inserted to keep a sorted array sorted?
A: This is a classic lower-bound binary search using the low < high template: whenever arr[mid] < target, move low = mid + 1; otherwise move high = mid. When the loop ends, low equals high and points to the first index whose value is >= target, which is exactly where the target should be inserted (whether or not it's already present).
int searchInsert(int[] arr, int target) {
int low = 0, high = arr.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}Q18. What is the difference between a "lower bound" and an "upper bound" binary search?
A: A lower bound finds the first index whose value is >= the target (the leftmost valid insertion point that keeps equal elements to the right of it, i.e., before any equal element). An upper bound finds the first index whose value is strictly > the target, effectively landing just past the last occurrence of an equal element. Subtracting lower bound from upper bound gives the count of elements equal to the target, mirroring the first/last occurrence trick.
Q19. How do you find a peak element in an array (an element strictly greater than its neighbors) using binary search?
A: Compare the middle element to its right neighbor: if arr[mid] < arr[mid + 1], the array is still rising, so a peak must exist somewhere to the right, and you search the right half; otherwise a peak exists at mid or to its left, so you search the left half including mid. This guarantees convergence to a valid peak in O(log n) because you always move toward increasing values.
int findPeakElement(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid;
}
return low;
}Q20. Why does the peak-finding binary search always converge to a valid answer, even without global sorting?
A: The algorithm relies only on the local comparison between adjacent elements, not on any global order, and array boundaries are treated as negative infinity, guaranteeing at least one peak exists. Each step moves toward a region where the sequence is "climbing," and since the array is finite, the climb must eventually stop at a peak. This is a good example of binary search applied to a condition (local monotonic direction) rather than to a literal sorted comparison.
Q21. How do you search for a target in a rotated sorted array (no duplicates) in O(log n)?
A: At each step, compare arr[low], arr[mid], and arr[high] to determine which half is "properly" sorted (not rotated). If the target's value falls within the sorted half's range, search that half; otherwise the target, if present, must be in the other half. This preserves O(log n) time because exactly one half is always contiguous and sorted, giving you a valid range check even though the whole array isn't sorted.
int searchRotated(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[low] <= arr[mid]) { // left half sorted
if (arr[low] <= target && target < arr[mid]) high = mid - 1;
else low = mid + 1;
} else { // right half sorted
if (arr[mid] < target && target <= arr[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}Q22. How does searching a rotated sorted array change when duplicates are allowed?
A: Duplicates can make arr[low] == arr[mid] == arr[high], so you can no longer reliably tell which half is sorted from that comparison alone. The fix is to shrink the range by one from both ends (low++; high--) whenever this ambiguous case occurs, falling back to a linear step. This degrades the worst-case complexity to O(n) (e.g., an array of all-equal values with one different element), which is an important trade-off to mention explicitly in an interview.
Q23. How do you find the minimum element in a rotated sorted array in O(log n)?
A: Use a boundary-style binary search: compare arr[mid] to arr[high]. If arr[mid] > arr[high], the minimum must be to the right of mid (the rotation point is there), so low = mid + 1; otherwise the minimum is at mid or to its left, so high = mid. When low equals high, that index holds the minimum, achieved in O(log n).
int findMin(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) low = mid + 1;
else high = mid;
}
return arr[low];
}Q24. How do you find the maximum element in a rotated sorted array?
A: The maximum sits immediately before the rotation point (the minimum), so you can reuse the minimum-finding binary search and return the element just before it — with wraparound handling if the minimum is at index 0, meaning the array wasn't rotated and the maximum is simply the last element. This keeps the approach O(log n) rather than an O(n) linear scan for the max.
Q25. How do you determine how many times a sorted array has been rotated?
A: The number of rotations equals the index of the minimum element, since rotating a sorted array k times moves the original index-0 element to index k. You find that index using the same O(log n) binary search used to locate the minimum in a rotated sorted array, then return the index directly as the rotation count.
Q26. What invariant is maintained at each step of binary search on a rotated sorted array?
A: The invariant is that at least one of the two halves defined by low, mid, and high is always a contiguous, properly sorted (non-rotated) subrange, because a single rotation point can only exist in one half at a time. This lets you always make a valid sorted-range membership check on at least one side, which is what allows the algorithm to safely discard half the search space every iteration, just like standard binary search.
Q27. How do you binary search a 2D matrix that is fully sorted in row-major order (each row's last element < next row's first element)?
A: Treat the matrix as a virtual 1D sorted array of size rows * cols and run standard binary search over indices 0 to rows*cols-1, converting each candidate 1D index back to (row, col) via row = idx / cols, col = idx % cols. This achieves O(log(rows × cols)) time and O(1) space, avoiding a full O(rows × cols) scan.
boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length;
int low = 0, high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int val = matrix[mid / cols][mid % cols];
if (val == target) return true;
else if (val < target) low = mid + 1;
else high = mid - 1;
}
return false;
}Q28. How do you search a matrix that is sorted row-wise and column-wise but not fully sorted as one flattened sequence?
A: Start at the top-right corner and compare it to the target: if equal, you're done; if the current value is greater than the target, move left (eliminating that column, since everything below is even larger); if smaller, move down (eliminating that row, since everything to the left is even smaller). Each step eliminates exactly one row or column, giving O(rows + cols) time and O(1) space — you can't use the flattened-array binary search trick here because the matrix isn't globally sorted as one sequence.
Q29. What's the complexity trade-off between the O(log(mn)) flattened binary search and the O(m+n) staircase search on 2D matrices?
A: The flattened O(log(mn)) approach only works when the matrix is fully sorted in row-major order — a stronger guarantee than "sorted rows and sorted columns" alone. The staircase O(m+n) approach handles the weaker, more common "sorted rows and sorted columns independently" case but is asymptotically worse for large square matrices (log(n²) = 2log(n) versus 2n). Choosing the wrong one either fails correctness (using flattened search on a non-row-major matrix) or leaves easy performance on the table.
Q30. How does binary search help find the median of two sorted arrays in O(log(min(m,n))) time?
A: Binary search on the smaller array's partition point: for a candidate partition, compute the corresponding partition in the other array such that the combined left portions have exactly half the total elements, then check if the largest left element on both sides is ≤ the smallest right element on both sides. If not, adjust the partition left or right, similar to standard binary search's low/high narrowing, until the correct partition is found, at which point the median is derivable from the four boundary elements in O(1).
double findMedianSortedArrays(int[] a, int[] b) {
if (a.length > b.length) { int[] t = a; a = b; b = t; }
int m = a.length, n = b.length, low = 0, high = m;
while (low <= high) {
int i = low + (high - low) / 2, j = (m + n + 1) / 2 - i;
int aLeft = (i == 0) ? Integer.MIN_VALUE : a[i - 1];
int aRight = (i == m) ? Integer.MAX_VALUE : a[i];
int bLeft = (j == 0) ? Integer.MIN_VALUE : b[j - 1];
int bRight = (j == n) ? Integer.MAX_VALUE : b[j];
if (aLeft <= bRight && bLeft <= aRight) {
if ((m + n) % 2 == 0) return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
return Math.max(aLeft, bLeft);
} else if (aLeft > bRight) high = i - 1;
else low = i + 1;
}
throw new IllegalArgumentException("Input arrays not sorted");
}Q31. What is "binary search on the answer" and when should you recognize it as the right pattern?
A: It's a technique where you binary search not over array indices but over the range of possible answer values (e.g., capacities, speeds, sizes), using a monotonic "is this value feasible?" check to decide which half of the value range to keep. You should recognize the pattern whenever a problem asks for the minimum (or maximum) value satisfying some condition, and increasing the candidate value only ever makes the condition easier (or only ever harder) to satisfy — that monotonicity is what makes binary search valid.
Q32. How do you compute the integer square root of a non-negative number using binary search?
A: Binary search over the candidate answer range [0, n], checking at each mid whether mid * mid <= n; if true, mid is a valid candidate so you record it and search higher (low = mid + 1), otherwise search lower (high = mid - 1). The last recorded valid candidate is floor(sqrt(n)), computed in O(log n) time versus repeated multiplication/incrementing which would be O(√n).
int mySqrt(int n) {
int low = 0, high = n, ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if ((long) mid * mid <= n) { ans = mid; low = mid + 1; }
else high = mid - 1;
}
return ans;
}Q33. How do you find the minimum ship capacity needed to ship all packages within D days using binary search on the answer?
A: The answer range is [max(weights), sum(weights)] — capacity can't be less than the heaviest single package, and never needs to exceed shipping everything in one day. For each candidate capacity, a greedy O(n) feasibility check simulates loading packages day by day and counts how many days are needed; if that count ≤ D, the capacity is feasible and you search lower, otherwise you search higher. This gives O(n × log(sum - max)) overall, far better than trying every capacity individually.
int shipWithinDays(int[] weights, int days) {
int low = 0, high = 0;
for (int w : weights) { low = Math.max(low, w); high += w; }
while (low < high) {
int mid = low + (high - low) / 2;
int daysNeeded = 1, load = 0;
for (int w : weights) {
if (load + w > mid) { daysNeeded++; load = 0; }
load += w;
}
if (daysNeeded <= days) high = mid; else low = mid + 1;
}
return low;
}Q34. How does the "Koko eating bananas" problem use binary search on the answer?
A: The answer range is [1, max(pileSizes)] — eating speed k. For a candidate k, compute the total hours needed as the sum of ceil(pile / k) for every pile; if that total is ≤ the hour limit h, k is feasible (search lower for a smaller valid k), otherwise search higher. This is O(n × log(max pile)) instead of testing every possible speed from 1 upward.
Q35. How does the "split array largest sum" problem use binary search on the answer?
A: You binary search over the possible value of "the largest subarray sum," bounded between max(single element) and total sum. For a candidate max-sum value, greedily partition the array into as few contiguous groups as possible without exceeding it; if the resulting group count is ≤ m (the allowed number of splits), the candidate is feasible and you try a smaller max-sum, otherwise you try a larger one. This turns an exponential partition-search problem into O(n log(sum)).
Q36. How does the "aggressive cows" (minimize the maximum, or maximize the minimum, distance) pattern use binary search on the answer?
A: Sort the stall positions, then binary search over the candidate minimum distance between any two cows, ranging from 1 to (max position - min position). For each candidate distance, greedily place cows one at a time, only placing the next cow once the gap from the last placed cow is >= the candidate; count how many cows fit. If enough cows fit, the candidate distance is feasible and you try a larger one, otherwise a smaller one — classic "maximize the minimum" binary search on answer.
Q37. How do you design the feasibility ("can we succeed with this value?") check for a binary-search-on-answer problem?
A: The check takes a candidate answer value and simulates the problem's constraints — usually with a single greedy linear pass — returning true/false (or a count to compare against a limit) for whether that candidate satisfies the requirement. It must run efficiently (commonly O(n)) since it's invoked O(log(range)) times, and it must be a pure function of the candidate value with no side effects that would break repeatability across binary search iterations.
Q38. Why must monotonicity hold for binary search on the answer to be valid?
A: Binary search only works correctly if the feasibility function is monotonic across the answer range — once it flips from infeasible to feasible (or vice versa), it must never flip back, because the algorithm's halving logic assumes each comparison reliably tells you which entire half to discard. If the feasibility function isn't monotonic, discarding a half based on one midpoint's result could throw away the actual answer, producing a wrong result silently rather than an error.
Q39. How do you find the smallest divisor such that the sum of ceiling-divided array elements is <= a threshold, using binary search?
A: Binary search the divisor over [1, max(array)]. For each candidate divisor, compute sum(ceil(num / divisor) for each num) in O(n); if that sum <= threshold, the divisor is feasible (a larger divisor only reduces the sum further, confirming monotonicity), so search for a smaller feasible divisor, otherwise search higher. This yields O(n log(max)) instead of testing every divisor linearly.
Q40. What is ternary search and how does it differ from binary search?
A: Ternary search splits the search range into three parts using two midpoints (mid1, mid2) instead of one, comparing the target or function value at both points to decide which third to discard. It's typically used to find the maximum/minimum of a unimodal function (one that strictly increases then strictly decreases, or vice versa) rather than for exact-value lookup in a sorted array, which is binary search's domain.
double ternarySearchMax(java.util.function.DoubleUnaryOperator f, double low, double high) {
for (int i = 0; i < 100; i++) {
double m1 = low + (high - low) / 3;
double m2 = high - (high - low) / 3;
if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) low = m1;
else high = m2;
}
return (low + high) / 2;
}Q41. When is ternary search preferred over binary search?
A: Ternary search is preferred specifically for finding an extremum (max or min) of a unimodal continuous function, where there's no simple "equal/less/greater" comparison to a fixed target — instead you're comparing the function's value at two candidate points to determine which direction has the extremum. It is not a general replacement for exact-match binary search on sorted arrays, where binary search is both simpler and asymptotically at least as good.
Q42. Why is binary search often still faster in practice than ternary search despite ternary search "sounding" more efficient?
A: Ternary search needs 2 function evaluations per iteration but only shrinks the range to 2/3 of its size, versus binary search's 1 evaluation shrinking to 1/2. Comparing information gained per evaluation, binary search actually requires fewer total function calls to reach the same precision (roughly log₂ versus (2/log₂(3/2))×log₂), so for the applicable cases where binary search is even usable, it typically wins on raw evaluation count.
Q43. What is exponential search and how does it work?
A: Exponential search first finds a range likely to contain the target by checking indices 1, 2, 4, 8, 16, ... (doubling each step) until either the target is found or an element larger than the target is encountered. It then runs standard binary search within that last doubled range (the previous bound to the current one). This combination is useful because it locates the correct range in O(log i) where i is the target's actual position, rather than assuming a fixed-size array upfront.
int exponentialSearch(int[] arr, int target) {
if (arr[0] == target) return 0;
int bound = 1;
while (bound < arr.length && arr[bound] < target) bound *= 2;
int low = bound / 2, high = Math.min(bound, arr.length - 1);
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Q44. When is exponential search particularly useful?
A: It shines when searching an unbounded or infinite-sized sorted sequence (like a stream with no known length, or an API that lazily generates elements), where you can't set up standard low/high indices ahead of time. It's also useful when the target is expected to be near the beginning of a very large array, since the doubling phase quickly narrows to a small range instead of committing to a full-array binary search from the start.
Q45. What is the time complexity of exponential search?
A: The doubling phase runs in O(log i) steps where i is the index of the target (or the array's end if the target is absent), and the subsequent binary search within the found range also costs O(log i). The combined complexity is O(log i), which matches standard O(log n) binary search when i is close to n, but can be faster when the target is near the front of a very large or unbounded array.
Q46. How do you search for a target in an array of unknown or effectively infinite size?
A: Use exponential search: probe increasingly large indices (doubling each time, handling out-of-bounds access gracefully, e.g., catching an exception or checking a provided "has element at index" query) until you either find the target or overshoot past it, then binary search the last bracketed range. This avoids needing to know the array's length in advance, which a standard low=0, high=length-1 binary search requires.
Q47. What is interpolation search and how does it differ from binary search?
A: Instead of always checking the middle element, interpolation search estimates the target's likely position using linear interpolation based on the target's value relative to the range's endpoint values — similar to how you'd guess a name's position in a phone book based on its first letter. The probe position is computed as low + (target - arr[low]) * (high - low) / (arr[high] - arr[low]), which converges much faster than a fixed midpoint when data is uniformly distributed.
int interpolationSearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high) return (arr[low] == target) ? low : -1;
int pos = low + (int) ((long) (target - arr[low]) * (high - low) / (arr[high] - arr[low]));
if (arr[pos] == target) return pos;
else if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}Q48. What is the average and worst-case time complexity of interpolation search?
A: On uniformly distributed sorted data, interpolation search averages O(log log n), a significant improvement over binary search's O(log n), because each probe lands very close to the actual target position. However, its worst case degrades to O(n) on skewed or exponentially distributed data, where the linear interpolation formula makes poor guesses repeatedly (e.g., most values clustered at one end with a few large outliers).
Q49. When does interpolation search perform poorly, and why?
A: It performs poorly on non-uniformly distributed data — for example, an array where most values are close together except for one huge outlier at the end — because the interpolation formula assumes roughly even spacing between values, and skewed distributions make its position estimates consistently far off. In such adversarial or naturally skewed cases, it can degrade to effectively linear O(n) behavior, which is why binary search's guaranteed O(log n) is often preferred unless the data's distribution is known and favorable.
Q50. What is jump search and how does it work?
A: Jump search scans a sorted array in fixed-size blocks (jumps), checking the last element of each block until it finds a block whose last element is >= the target, then performs a linear scan within that block to find the exact position. It trades some of binary search's efficiency for simpler, more cache-friendly sequential memory access, especially useful on data structures where "jumping back" (random access) is expensive but stepping forward by a fixed amount is cheap.
int jumpSearch(int[] arr, int target) {
int n = arr.length;
int step = (int) Math.sqrt(n);
int prev = 0, curr = 0;
while (curr < n && arr[curr] < target) {
prev = curr;
curr = Math.min(curr + step, n);
}
for (int i = prev; i < Math.min(curr, n); i++) {
if (arr[i] == target) return i;
}
return -1;
}Q51. What is the optimal block size for jump search, and why is √n the right choice?
A: With block size m, the number of jumps is at most n/m and the final linear scan within a block costs at most m, so total work is n/m + m. This expression is minimized by calculus (or AM-GM inequality) when m = √n, giving a total cost of O(√n) — any smaller or larger block size increases the sum of the two terms.
Q52. What is the time complexity of jump search, and where does it sit between linear and binary search?
A: Jump search runs in O(√n) time, strictly worse than binary search's O(log n) but strictly better than linear search's O(n) for large n. It's chosen in practice specifically when backward random-access jumps are expensive (some external storage or streaming scenarios) but binary search's back-and-forth index jumps would be costly, making the simpler forward-only jump pattern a worthwhile trade-off.
Q53. How does Java's Arrays.binarySearch() behave when the target element isn't found?
A: It returns a negative value encoding the insertion point: specifically -(insertionPoint) - 1, where insertionPoint is the index where the target would need to be inserted to keep the array sorted. This lets callers both detect "not found" (any negative result) and recover the correct insertion point via -(result) - 1, without a second lookup.
int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 6);
// idx is negative since 6 isn't present
int insertionPoint = -(idx) - 1; // where 6 should go: index 3
System.out.println(insertionPoint);Q54. How does Collections.binarySearch() differ from Arrays.binarySearch()?
A: Collections.binarySearch() operates on any List implementing RandomAccess (like ArrayList) efficiently in O(log n); for lists without efficient random access (like LinkedList), it falls back to a sequential-access strategy that degrades toward O(n), because true O(log n) binary search fundamentally requires O(1) index access. Both methods share the same negative-result-encodes-insertion-point convention for "not found."
Q55. What happens if you call Arrays.binarySearch() on an array that isn't actually sorted?
A: The method has no way to detect that the precondition is violated, so it silently produces an unspecified, unreliable result — it might return a wrong index, a false "not found," or even a false "found" for the wrong reasons, depending on how the comparisons happen to fall. This is a dangerous silent-failure mode; the JavaDoc explicitly states behavior is undefined if the array isn't sorted, so it's the caller's responsibility to guarantee sortedness beforehand.
Q56. How do you use Arrays.binarySearch() with a custom Comparator for objects?
A: Overload Arrays.binarySearch(T[] array, T key, Comparator<? super T> comparator) lets you search an array of objects sorted according to a custom order rather than their natural Comparable ordering. The array must already be sorted using that exact same comparator, or results are again unspecified — consistency between the sort comparator and the search comparator is essential.
String[] names = {"charlie", "alice", "bob"};
Comparator<String> byLength = Comparator.comparingInt(String::length);
Arrays.sort(names, byLength);
int idx = Arrays.binarySearch(names, "bob", byLength);Q57. What is the return value convention -(insertion point) - 1 used for, and why not just return -1 for "not found"?
A: Returning plain -1 would discard useful information about where the target would belong if it needed to be inserted, forcing a second search to recover that. The -(insertionPoint) - 1 encoding is a bijection between "found at index i" (non-negative i) and "not found, would insert at index j" (negative, recoverable as -result - 1), so one call serves both search and insertion-point use cases, and the encoding is reversible without ambiguity for any valid array index including 0.
Q58. How do you binary search only a subrange of an array using Java's Arrays.binarySearch(array, fromIndex, toIndex, key)?
A: This overload restricts the search to indices [fromIndex, toIndex), which must itself already be sorted (the rest of the array can be anything). It's useful when you've partitioned a larger array and know only a specific segment is sorted and relevant, avoiding the overhead or incorrectness of searching the whole array.
int[] arr = {9, 9, 1, 3, 5, 7, 9, 9};
// only indices [2, 6) are sorted: {1, 3, 5, 7}
int idx = Arrays.binarySearch(arr, 2, 6, 5); // searches within that subrange onlyQ59. Why must the input be sorted before calling Arrays.binarySearch(), and what's the practical risk of forgetting?
A: Binary search's correctness fundamentally depends on being able to eliminate half the remaining elements based on a single comparison, which is only valid if all elements on one side of that comparison point are guaranteed <= (or >=) the target. In practice, forgetting to sort first is a silent bug — no exception is thrown, and the method may even occasionally "work" by luck on small or partially-ordered test data, masking the bug until it fails unpredictably in production with different data.
Q60. How would you implement your own generic binary search utility method for any Comparable type in Java?
A: Use a bounded generic type parameter <T extends Comparable<T>> so the method works for any type with natural ordering, and call compareTo() instead of primitive comparison operators. The overall structure (low, high, mid, narrowing) is identical to the primitive int version; only the comparison mechanism changes.
<T extends Comparable<T>> int genericBinarySearch(T[] arr, T target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int cmp = arr[mid].compareTo(target);
if (cmp == 0) return mid;
else if (cmp < 0) low = mid + 1;
else high = mid - 1;
}
return -1;
}Q61. What is the difference between recursive and iterative binary search in terms of stack usage in Java?
A: The recursive version pushes a new stack frame for each call, consuming O(log n) additional stack space that grows with input size, whereas the iterative version reuses the same stack frame throughout, needing only O(1) extra space regardless of array size. For extremely large arrays or in stack-constrained environments (e.g., deeply nested concurrent tasks), the iterative form is the safer default.
Q62. Can binary search cause a StackOverflowError, and under what circumstances?
A: Yes, in theory, if implemented recursively on an astronomically large array (or, more realistically, if a bug causes the recursion to fail to converge, effectively looping forever with growing depth), the recursion depth could exceed the JVM's stack size and throw StackOverflowError. In practice, O(log n) recursion depth is tiny even for huge arrays (log₂ of a billion is under 30), so this is far more likely to happen from a logic bug than from legitimate array size alone.
Q63. How do you find the square root of a number to a given decimal precision using binary search on floating-point values?
A: First find the integer part via integer binary search, then binary search the fractional part over a floating-point range, narrowing low/high as doubles and checking mid * mid against the target with a fixed number of iterations (or until high - low is smaller than the desired precision), since floating-point comparisons for exact equality are unreliable.
double sqrtPrecise(double n, double precision) {
double low = 0, high = Math.max(1, n);
while (high - low > precision) {
double mid = (low + high) / 2;
if (mid * mid < n) low = mid; else high = mid;
}
return (low + high) / 2;
}Q64. How do you adapt binary search for an array sorted in descending order?
A: Flip the comparison direction: if arr[mid] < target, the target (being larger) must be to the left since values decrease rightward, so high = mid - 1; if arr[mid] > target, move low = mid + 1. Everything else about the algorithm's structure — halving, O(log n) time — stays identical; only the direction of the two branches is mirrored.
int searchDescending(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) low = mid + 1; // reversed
else high = mid - 1; // reversed
}
return -1;
}Q65. How do you adapt binary search to find the element closest to a target when an exact match may not exist?
A: Run a standard binary search; if the target is found, return it. If not found, the loop ends with low and high adjacent (low = high + 1), so compare arr[high] (just below target) and arr[low] (just above target, careful with bounds) and return whichever is numerically closer to the target. This still runs in O(log n) since it's just binary search plus a constant-time final comparison.
Q66. How do you find the floor (largest element <= target) and ceiling (smallest element >= target) of a value in a sorted array using binary search?
A: Run a single binary search tracking two candidate answers as you go: whenever arr[mid] <= target, update the floor candidate and move low = mid + 1; whenever arr[mid] >= target, update the ceiling candidate and move high = mid - 1. Both converge in the same O(log n) pass since the two conditions overlap exactly when arr[mid] == target.
int[] floorCeil(int[] arr, int target) {
int low = 0, high = arr.length - 1, floor = -1, ceil = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return new int[]{arr[mid], arr[mid]};
if (arr[mid] < target) { floor = arr[mid]; low = mid + 1; }
else { ceil = arr[mid]; high = mid - 1; }
}
return new int[]{floor, ceil};
}Q67. What is a common mistake when computing mid for binary search on an answer space that includes negative bounds?
A: Using integer division naively ((low + high) / 2) when low is negative can round toward zero instead of toward negative infinity in Java, subtly shifting mid in a way that breaks the intended narrowing direction near zero. The safer pattern, low + (high - low) / 2, avoids this because high - low is always non-negative when high >= low, sidestepping the negative-number rounding inconsistency entirely.
Q68. What's the risk of integer overflow in binary search boundary computation, and how do you avoid it generally?
A: If low and high are both large positive ints (common in answer-space binary search over big ranges like sums or capacities), low + high can exceed Integer.MAX_VALUE and wrap to a negative number, producing a nonsensical mid. Avoid it by using low + (high - low) / 2, or by widening to long arithmetic for the boundary variables when the range could plausibly approach the int limit.
Q69. How do you binary search on a "valley" function (strictly decreasing then strictly increasing) to find its minimum?
A: Compare f(mid) to f(mid + 1): if f(mid) > f(mid + 1), the function is still descending, so the minimum lies to the right, and you move low = mid + 1; otherwise the minimum is at mid or to the left, so high = mid. This mirrors the peak-finding logic exactly but inverted, converging to the valley's bottom in O(log n).
Q70. How do you find the single non-duplicate element in a sorted array where every other element appears exactly twice?
A: Binary search on even indices only: before the single element, pairs are aligned so that the first of each pair sits at an even index (arr[even] == arr[even+1]); after the single element, that alignment breaks. Check arr[mid] where mid is forced to an even index — if it equals arr[mid+1], the single element is to the right (low = mid + 2), otherwise it's at mid or to the left (high = mid). This achieves O(log n) instead of an O(n) XOR-based linear scan.
int singleNonDuplicate(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (mid % 2 == 1) mid--;
if (arr[mid] == arr[mid + 1]) low = mid + 2;
else high = mid;
}
return arr[low];
}Q71. Why is binary search rarely used directly on linked lists, even sorted ones?
A: Binary search's O(log n) time bound relies on O(1) random access to the middle element at every step, but a singly (or even doubly) linked list only offers O(n) access to an arbitrary node by walking pointers from the head or tail. Applying the standard binary search algorithm to a linked list would make each "jump to mid" cost O(n), degrading total time to O(n log n) — worse than a simple O(n) linear scan.
Q72. What data structure property is essential for binary search to achieve O(log n), beyond just being sorted?
A: Random access — the ability to jump directly to any index in O(1) time — is essential; sortedness alone only guarantees that a valid halving decision can be made, not that reaching the midpoint is cheap. Arrays satisfy this because of contiguous memory layout, but sorted structures like linked lists or certain balanced trees without index support don't, which is why binary search is typically taught and applied on arrays specifically.
Q73. What is the "search space" abstraction, and why is it a useful mental model for binary-search-based interview problems?
A: The search space is the full set of candidate values (indices or answer values) that could possibly be correct, and binary search is fundamentally a strategy for eliminating half of that space per step using one comparison. Framing a new problem by asking "what is my search space, and is there a monotonic yes/no check over it?" is often the fastest way to recognize that binary search applies at all, even when the problem doesn't look like a classic sorted-array lookup on the surface.
Q74. How do you find the kth smallest element in a row- and column-sorted matrix using binary search?
A: Binary search over the value range [matrix[0][0], matrix[n-1][n-1]]. For each candidate value, count how many elements in the matrix are <= it in O(n) using the staircase technique (starting from the bottom-left, moving right when the current value is <= candidate, otherwise moving up). If that count >= k, the kth smallest is <= candidate, so search lower; otherwise search higher — giving O(n log(max-min)) overall instead of extracting and sorting all n² elements.
int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int low = matrix[0][0], high = matrix[n - 1][n - 1];
while (low < high) {
int mid = low + (high - low) / 2;
int count = 0, col = n - 1;
for (int row = 0; row < n; row++) {
while (col >= 0 && matrix[row][col] > mid) col--;
count += col + 1;
}
if (count < k) low = mid + 1; else high = mid;
}
return low;
}Q75. How would you binary search to find the smallest letter in a sorted circular list of letters that is strictly greater than a target letter?
A: Use the lower/upper-bound binary search template: search for the first index whose letter is strictly greater than the target (low < high, moving low = mid + 1 when letters[mid] <= target, else high = mid). Because the list is circular, if the final low index equals the array length, wrap around and return index 0 instead, representing "the smallest letter overall."
Q76. How would you explain binary search's correctness in an interview using a loop invariant?
A: State the invariant explicitly: "if the target exists in the array, it always lies within [low, high] at the start of every iteration." Show that the invariant holds initially (the full array), is preserved by each branch (each branch only discards a region proven not to contain the target), and that the loop terminates because the range strictly shrinks each iteration — together these three points (initialization, maintenance, termination) constitute a rigorous correctness proof interviewers appreciate.
Q77. What edge cases should you test a binary search implementation against?
A: Test an empty array (should return "not found" without crashing), a single-element array (both matching and non-matching target), a target smaller than every element, a target larger than every element, duplicates surrounding the target, and a target that would need to be found at index 0 or the last index specifically (to catch off-by-one boundary errors). Systematically covering these edge cases catches the vast majority of real binary search bugs before they reach production.
Q78. What's the practical difference between a binary search that returns "any matching index" versus one guaranteed to return a deterministic first or last match?
A: "Any match" binary search is simpler and sufficient when you only need to know a target exists or retrieve one instance of it, and it terminates as soon as a match is found. A deterministic first/last search is necessary whenever downstream logic depends on a specific boundary — e.g., computing a range's size, or inserting a new element in a stable position relative to duplicates — and it requires continuing the search past the first match found, costing the same O(log n) but touching slightly more comparisons in practice.
Q79. What pitfalls arise when binary searching over floating-point numbers instead of integers?
A: Exact equality checks (== target) are unreliable with floating-point arithmetic due to representation and rounding error, so floating-point binary search typically loops for a fixed number of iterations or until the range width (high - low) shrinks below a chosen epsilon, rather than checking for an exact match. You also can't rely on integer-style "narrow to a single index" termination since there's no discrete "next" float value in a conceptually continuous range.
Q80. How would you find the peak index in a "mountain array" (strictly increasing then strictly decreasing)?
A: This is a direct application of the peak-finding binary search: compare arr[mid] to arr[mid + 1]; if increasing, move right (low = mid + 1), otherwise move left (high = mid). Because a mountain array guarantees exactly one peak and strict monotonic segments on each side, the algorithm converges to that unique peak in O(log n) with no ambiguity.
int peakIndexInMountainArray(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid;
}
return low;
}Q81. How would you verify whether a given array actually qualifies as a valid "mountain array" before running peak-search logic on it?
A: Walk up from the start while values strictly increase, then walk down from where that stopped while values strictly decrease; the array is a valid mountain only if both phases together consume the entire array, the increasing phase isn't empty (the peak isn't at index 0), and the decreasing phase isn't empty (the peak isn't at the last index). This O(n) validation is worth doing explicitly, since blindly running the O(log n) peak search on a non-mountain array (e.g., strictly increasing with no descent) can return a misleading result.
Q82. How do you use a "bisect"-style binary search to find where a new element should be inserted to keep a list sorted?
A: This is exactly the lower-bound / search-insert-position pattern: binary search for the first index whose element is >= the new value, using the low < high boundary template. Python's bisect.insort and Java's Arrays.binarySearch insertion-point encoding both rely on this same underlying idea, just exposed through different APIs.
Q83. What's the complexity difference between binary search on a sorted array and searching a balanced binary search tree?
A: Both are O(log n) for a balanced structure, but they differ in access pattern and mutability trade-offs: array-based binary search requires O(n) to insert or delete (due to shifting), while a balanced BST supports O(log n) insert/delete alongside O(log n) search, at the cost of extra pointer overhead and worse cache locality than a contiguous array. Choosing between them in a system design context depends on whether the data is mostly static (favoring sorted arrays) or frequently mutated (favoring balanced trees or skip lists).
Q84. How would binary search combine with another algorithm to solve a "minimum effort path" style grid problem?
A: Binary search over the candidate "maximum allowed effort" value; for each candidate, run a graph traversal (BFS/DFS, or a variant of Dijkstra) that only moves between cells whose height difference is <= the candidate, checking whether a path from start to end exists at all under that constraint. If a path exists, the candidate is feasible and you search for a smaller max effort; otherwise search higher — combining O(log(maxDiff)) binary search iterations with an O(rows × cols) traversal each time.
Q85. How would you binary search on the answer for a "minimum days to make m bouquets, each needing k adjacent bloomed flowers" problem?
A: Binary search over the candidate number of days, bounded by [min(bloomDay), max(bloomDay)]. For a candidate day count, mark flowers with bloomDay <= candidate as bloomed, then greedily scan for consecutive runs of k bloomed flowers to count how many complete bouquets can be formed; if that count >= m, the candidate day count is feasible and you search for fewer days, otherwise more days are needed. This is O(n log(range)) versus simulating every single day count individually.
Q86. What is the general three-part template for binary search on the answer?
A: First, define the answer's plausible range [low, high] based on problem constraints (e.g., smallest and largest theoretically valid values). Second, write a feasibility function that, given a candidate value, determines in reasonable time whether that value satisfies the requirement. Third, binary search over the range using that feasibility check to decide which half to keep, converging on the minimal (or maximal) feasible value depending on whether you're minimizing or maximizing.
Q87. How do you handle binary search when the target value could fall entirely outside the array's stored value range?
A: The algorithm naturally handles this correctly without special-casing: if the target is smaller than every element, the search narrows and eventually returns "not found" (or an insertion point of 0); if larger than every element, it converges similarly to "not found" (or an insertion point equal to the array length). The important part is ensuring your loop's termination and return-value logic don't assume the target must be present, and that boundary checks like array-length insertion points are handled without an index-out-of-bounds error.
Q88. When should you use the low <= high exact-match template versus the low < high boundary-convergence template?
A: Use low <= high when you're looking for an exact match and need to explicitly check the case where low and high point to the same single remaining candidate. Use low < high when you're converging toward a boundary (first true, last false, minimum, peak) where you never need to "check" the final low==high position inside the loop — you simply return low or high once they've merged, since the invariant guarantees it's already the answer.
Q89. Why do candidates who understand binary search conceptually still often get the code wrong in interviews?
A: The core idea (halving a sorted range) is simple, but the exact boundary conditions — whether to use mid - 1/mid + 1/mid, which loop condition to use, and how mid rounding interacts with those choices — vary between the "exact match" and "boundary" templates, and mixing them under time pressure produces subtle off-by-one bugs or infinite loops. Practicing a small, memorized set of correct templates (rather than re-deriving from scratch each time) is the most reliable way to avoid this in a live interview.
Q90. What's a good mental model for deciding between low = mid + 1, high = mid - 1, and high = mid at each step?
A: Ask: "after this comparison, is mid itself still a possible answer?" If mid has been fully ruled out (e.g., exact-match search and arr[mid] != target), exclude it with +1/-1. If mid could still be the answer (e.g., in a boundary search where mid satisfies the condition but a better one might exist further in the same direction), keep it in range with plain high = mid (never excluding mid), and pair that with the low<high loop template to avoid infinite loops.
Q91. How do you binary search a sorted array to find the count of elements less than or equal to a given value?
A: Find the upper bound (first index strictly greater than the value) using the boundary binary search template; that index itself equals the count of elements <= the value, since every element before it satisfies the condition and every element at or after it doesn't. This is O(log n), versus an O(n) linear count.
Q92. How would you find a missing number in a sorted array of otherwise-consecutive integers using binary search?
A: In a fully consecutive array, arr[i] == arr[0] + i for every index. Binary search for the first index where this equality breaks (arr[mid] != arr[0] + mid), moving right when the equality still holds (missing number is further right) and left otherwise; the missing value is arr[0] + low once the loop converges. This is O(log n) instead of an O(n) scan for the break point.
Q93. Why is binary search considered a "divide and conquer" algorithm?
A: Divide and conquer algorithms split a problem into smaller subproblems, solve them, and combine results; binary search divides the search range into two halves (splitting), determines via one comparison which half could possibly contain the answer (effectively "solving" the irrelevant half trivially by discarding it), and recurses only into the relevant half. Unlike merge sort, it never needs to "combine" two solved halves, since only one half is ever explored — but the divide step is the same conceptual move.
Q94. How does binary search's O(log n) complexity compare to a hash-based O(1) lookup, and when would you still prefer binary search?
A: A hash table offers O(1) average-case lookup, asymptotically better than binary search's O(log n), so for pure "does this key exist" queries a hash table usually wins. Binary search remains preferable when you need order-dependent operations a hash table can't do efficiently — range queries, finding nearest neighbors, first/last occurrence, or predecessor/successor lookups — because sorted array structure preserves relative ordering that hashing intentionally discards.
Q95. How would you binary search for a target in a bitonic array (strictly increases then strictly decreases)?
A: First find the peak index using the standard O(log n) peak-finding binary search. Then run a normal ascending binary search on the portion before the peak, and a descending-order binary search (comparison flipped) on the portion after the peak; the target, if present, will be found by exactly one of those two searches. Total cost remains O(log n) since it's three sequential O(log n) searches.
Q96. Why are "leftmost/rightmost" binary search variants especially relevant to real systems like log or timestamp lookups?
A: Real-world queries like "find the first log entry at or after time T" or "find the last entry before time T" are naturally leftmost/rightmost boundary searches over a timestamp-sorted sequence, not exact-value equality lookups (an exact timestamp match is rarely what's needed). Databases and log systems implement range-scan starting points using exactly this pattern internally, which is why understanding the boundary-search template generalizes directly to production system design, not just algorithm puzzles.
Q97. How would you implement a binary-search-based lookup for the range of strings sharing a given prefix in a sorted string array (an autocomplete boundary problem)?
A: Compute the lower bound as the first index whose string is >= the prefix, and the upper bound as the first index whose string is >= the prefix with its last character incremented (or, more robustly, the first string that doesn't start with the prefix) — both via standard O(log n) boundary binary searches on the sorted array using appropriate string comparisons. The range between those two bounds contains exactly the strings sharing that prefix, giving O(log n + k) total where k is the number of matches, versus an O(n) linear filter.
int lowerBoundPrefix(String[] words, String prefix) {
int low = 0, high = words.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (words[mid].compareTo(prefix) < 0) low = mid + 1;
else high = mid;
}
return low;
}Q98. How do you binary search on an answer that must satisfy multiple constraints simultaneously?
A: As long as the combined feasibility check — evaluating all constraints together for a given candidate answer — remains monotonic over the answer range, you can still binary search using that single combined check as a black box, exactly as with a single-constraint problem. The complexity of the check itself simply grows to account for evaluating every constraint, but the outer binary search structure (O(log range) iterations) doesn't change.
Q99. What's an example of binary search misapplication, and why does it fail on non-monotonic data?
A: Applying binary search directly to an unsorted array, or to an answer-space problem where increasing the candidate value sometimes helps and sometimes hurts feasibility (no consistent monotonic boundary), breaks the core assumption that one comparison can safely discard half the space. The algorithm won't crash or throw an error — it will simply return a plausible-looking but incorrect answer, silently discarding the region that actually contained the correct one, which makes this class of bug notoriously hard to catch in testing.
Q100. How would you find a "fixed point" in a sorted array of distinct integers — an index i where arr[i] == i — using binary search?
A: Because the array is sorted with distinct values, arr[mid] - mid is non-decreasing as mid increases, giving a monotonic property to binary search on: if arr[mid] == mid, return mid; if arr[mid] < mid, the fixed point (if any) must be to the right, so low = mid + 1; otherwise it must be to the left, so high = mid - 1. This achieves O(log n) instead of an O(n) linear scan checking every index.
int fixedPoint(int[] arr) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == mid) return mid;
else if (arr[mid] < mid) low = mid + 1;
else high = mid - 1;
}
return -1;
}Q101. How would you combine binary search with a two-pointer scan to find a pair with a given difference in a sorted array?
A: For each element, binary search for element + difference in the remaining array, giving O(n log n) total — a reasonable answer, though a pure two-pointer scan (advancing one pointer when the current difference is too small, the other when too large) solves the same problem in O(n) without any per-element binary search, since the array is already sorted. Mentioning both and explaining why the two-pointer approach is strictly better here demonstrates a more complete understanding.
Q102. How would you explain the time-complexity trade-off of binary search versus linear search to a non-technical stakeholder?
A: Analogize it to searching a phone book: flipping through every page one at a time (linear search) versus opening to the middle, checking which half the name falls in, and repeating (binary search) — for a million-entry phone book, linear search might take up to a million checks while binary search takes about 20. The key caveat to mention is that binary search's trick only works because the phone book is alphabetically sorted; an unsorted list forces you back to checking everything.
Q103. How would you set up the binary-search-on-answer template for a "minimum eating speed" style problem in general terms?
A: Define low as the smallest speed that could ever matter (often 1) and high as the largest single-item size (since a faster speed than the largest item wastes capacity). Write a feasibility function that computes total time/units needed at a candidate speed and compares it against the limit, then binary search using low < high, moving high = mid when feasible and low = mid + 1 when not, so that low converges to the minimum feasible speed.
Q104. What is the "binary search on prefix sums" pattern, and how does it combine with prefix sums for range queries?
A: After building a prefix-sum array in O(n), you can binary search within it to answer questions like "what's the smallest range ending at index j whose sum is >= k" (useful when all values are non-negative, since prefix sums are then monotonically non-decreasing, satisfying binary search's precondition). This combines an O(n) prefix-sum build with O(log n) per-query lookups, turning what might otherwise be O(n) per query into O(log n) per query after the one-time O(n) setup.
Q105. How would you solve the classic "first bad version" problem (finding the first failing version in a CI/build pipeline) with binary search?
A: The versions form a monotonic sequence: all versions before the first bad one are good, all versions from it onward are bad, which is exactly the boundary-search precondition. Binary search using the low < high template: if isBadVersion(mid) is true, the first bad version is at mid or earlier, so high = mid; otherwise it's later, so low = mid + 1. This finds the exact first bad version in O(log n) calls to the (possibly expensive) isBadVersion check, instead of testing every version linearly.
int firstBadVersion(int n) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
if (isBadVersion(mid)) high = mid;
else low = mid + 1;
}
return low;
}Q106. What edge case must a binary search implementation handle when the target is smaller than every element or larger than every element?
A: The loop must terminate correctly (low exceeding high) and the "not found" return path must not attempt to dereference an out-of-bounds index — a common bug is assuming the loop always ends with low and high pointing to valid array positions, when in fact low can end up equal to the array's length (one past the end) if the target exceeds everything. Explicitly testing both extremes catches this before it causes an ArrayIndexOutOfBoundsException in related boundary-search variants that index into the array after the loop.
Q107. How would you determine whether an interviewer expects an O(log n) binary search solution versus an acceptable O(n) approach?
A: Look for explicit signals in the problem statement — words like "sorted array," constraints suggesting a very large input size (e.g., n up to 10⁵), or the interviewer directly asking "can you do better than O(n)?" after you present a linear solution. When in doubt, it's good practice to state the O(n) approach first as a working baseline, then explicitly propose optimizing to O(log n) via binary search, showing you understand both the correctness-first and complexity-optimization phases of problem solving.
Q108. What's the difference between exponential search's doubling phase and its final binary search phase?
A: The doubling phase (checking indices 1, 2, 4, 8, ...) is a coarse, exponential probe used purely to quickly bracket a range likely containing the target without knowing the array's effective size upfront; it runs in O(log i) steps. The final phase then runs an ordinary O(log i) binary search, but confined to just that bracketed range (from the last successful doubled index to the first unsuccessful one), which is much smaller than the full array, making the combined approach efficient overall.
Q109. How would you use binary search to count the number of negative numbers in a matrix where each row is sorted in descending order?
A: For each row, binary search (on the descending-order template) for the first index where the value becomes negative; the count of negatives in that row is rowLength - firstNegativeIndex. Summing this across all rows gives O(rows × log(cols)) total, better than an O(rows × cols) full scan, though an O(rows + cols) staircase approach (starting from a corner) can be even faster by exploiting both row and column sorting simultaneously.
Q110. How does binary search correctness reasoning differ for an array with an even versus odd number of elements?
A: It doesn't actually differ in a way that requires separate code paths — integer division in mid = low + (high - low) / 2 naturally rounds down regardless of whether the current range has an even or odd count of elements, and the algorithm's invariants (target always within [low, high] if present) hold uniformly. The only place parity matters is in boundary-search templates choosing between rounding mid up or down to avoid infinite loops, which is a template-choice issue rather than an odd/even array-size issue.
Q111. What's a real-world system that uses binary-search-like logic internally?
A: Database engines use binary search (or B-tree node search, a generalized multi-way variant of the same idea) to quickly locate rows within sorted index pages, turning what would be a full table scan into a logarithmic lookup. Similarly, many range-partitioned distributed systems binary search over sorted partition boundaries to route a key to the correct shard in O(log(number of shards)) instead of checking every shard.
Q112. How does git bisect serve as a real-world analogy for explaining binary search on an answer space?
A: git bisect finds the commit that introduced a bug by binary searching over a monotonic timeline of commits: you mark a candidate commit as "good" or "bad," and the tool halves the remaining range each time based on that single feasibility check, just like binary search on the answer converges on a threshold value using a feasibility function. It's a genuinely production-grade application of exactly the same algorithmic idea taught in interviews, which makes it a strong, credible example to cite when explaining the pattern.
Q113. How does interpolation search's O(log log n) average case relate to information-theoretic lower bounds on comparison-based search?
A: The classic information-theoretic lower bound of ⊥log₂(n+1)⌈ comparisons applies to comparison-based search that only learns "less than / equal / greater than" from each probe; interpolation search circumvents this bound's practical implications by using the actual numeric values (not just their relative order) to make a much better-informed guess about position, which is why it can beat the standard O(log n) comparison-based bound on suitably distributed data. It doesn't violate the lower bound for pure comparison-based algorithms — it simply isn't restricted to comparisons alone, since it uses arithmetic on the values.
Q114. How do you design binary search to return a useful boundary index (rather than -1) when the exact target isn't found, so the result is usable for insertion?
A: Use the lower-bound/boundary template (low < high, moving toward the first index >= target) instead of the exact-match template; when the loop ends, low always holds a meaningful index — either the target's position if present, or the correct insertion point if absent — with no separate "not found" sentinel needed. This is exactly the approach Java's Arrays.binarySearch insertion-point encoding and Python's bisect_left both rely on internally.
Q115. What checklist would you mentally run through before writing binary search code in an interview to avoid the common bugs?
A: Confirm the input is genuinely sorted (or the answer space is monotonic) before anything else; decide up front whether you need the exact-match template (low <= high) or a boundary template (low < high) and stick to it consistently; use low + (high - low) / 2 to avoid overflow; make sure every branch either excludes mid (mid ± 1) or explicitly keeps it (= mid) in a way consistent with your chosen template; and finally trace through a tiny 1-2 element example by hand before trusting the code on the full problem.
Post a Comment
Add