Binary search interview questions, with answers

The questions, with answers

1. 1.How does binary search work, and why is it O(log n)?

   On a sorted array, compare the target with the middle element. If they match, done; if the target is smaller, the answer can only be in the left half; if larger, only in the right half. Each comparison discards half of the remaining range, so after k steps the range has n / 2^k elements, and it reaches one element after about log2(n) steps — twenty comparisons for a million elements, thirty for a billion. Two preconditions are worth stating: the data must be sorted, and you need O(1) access to the middle element, which is why binary search suits arrays and not linked lists.

   int search(int[] a, int target) {
       int lo = 0, hi = a.length - 1;
       while (lo <= hi) {
           int mid = lo + (hi - lo) / 2;
           if (a[mid] == target) return mid;
           if (a[mid] < target) lo = mid + 1;
           else hi = mid - 1;
       }
       return -1;   // not present
   }

2. 2.Why is mid = (low + high) / 2 a bug, and what should you write instead?

   Because low + high can overflow a fixed-width integer. With a 32-bit int, an array of over a billion elements can put low + high past 2^31 - 1, at which point the sum wraps negative, mid becomes a negative index, and the program throws or reads garbage. This exact bug sat in java.util.Arrays.binarySearch until 2006. Write mid = low + (high - low) / 2, which never exceeds high, or in Java the unsigned shift (low + high) >>> 1, which treats the overflowed sum as unsigned. Python's arbitrary-precision integers make it a non-issue there, but say why, not just that.

3. 3.How do you find the first and last occurrence of a value in a sorted array with duplicates?

   Don't stop at the first match. For the first occurrence, when a[mid] equals the target, record mid and keep searching the left half (high = mid - 1); for the last occurrence, record it and search the right half. Each is one binary search, so both bounds cost O(log n) together, and their difference plus one is the count of occurrences — a common follow-up. The general form is the lower-bound / upper-bound pair from C++'s standard library: lower_bound returns the first index with a value not less than the target, upper_bound the first index with a value greater than it, and the target is present exactly when they differ.

   int firstIndex(int[] a, int target) {
       int lo = 0, hi = a.length - 1, ans = -1;
       while (lo <= hi) {
           int mid = lo + (hi - lo) / 2;
           if (a[mid] == target) { ans = mid; hi = mid - 1; }   // keep looking left
           else if (a[mid] < target) lo = mid + 1;
           else hi = mid - 1;
       }
       return ans;
   }

4. 4.How do you search a rotated sorted array in O(log n)?

   A sorted array rotated at some pivot, such as 4 5 6 7 0 1 2, is two sorted runs. At every step at least one half — the one not containing the pivot — is sorted, and you can tell which by comparing a[low] with a[mid]. If the left half is sorted and the target lies between a[low] and a[mid], search there; otherwise search the right half, and symmetrically when the right half is the sorted one. You still halve the range each step, so it stays O(log n). With duplicates the test a[low] == a[mid] can be ambiguous, and the worst case degrades to O(n) — mention that if the interviewer asks about duplicates, because it is what they are checking.

5. 5.When is linear search the right choice over binary search?

   When the data is not sorted and you will only search it once — sorting costs O(n log n), more than the O(n) scan you were trying to avoid. When n is tiny, where the constant factors and branch predictability of a linear scan beat the log. When the container has no random access, such as a linked list, where the middle element costs O(n) to reach. And when the data changes constantly, since keeping it sorted for binary search costs O(n) per insertion into an array. Binary search wins when you sort once and search many times, or when the data is already sorted — and a hash table beats both for exact-match lookup at O(1) average.

6. 6.What is "binary search on the answer"?

   Applying binary search not to an array but to the range of possible answers, whenever a yes/no check on a candidate answer is monotonic — if a value works, every larger (or every smaller) value also works. Classic placement examples: the smallest ship capacity that delivers all packages within D days, the minimum time for k machines to finish n jobs, the largest square you can carve, and computing an integer square root. You binary search over the candidate values, call the checker at each midpoint, and move the boundary toward the smallest feasible value. The cost is O(log(range) × cost of the check), and recognising the monotonic structure is the whole skill.

7. 7.How do you write a binary search loop that never hangs or skips the answer?

   Pick one invariant and keep it. In the closed form, the answer, if present, is always in [low, high]; the loop runs while low <= high, and each branch moves strictly past mid (low = mid + 1 or high = mid - 1), so the range shrinks every step and cannot loop forever. In the half-open form used for lower bound, the answer is in [low, high), the loop runs while low < high, the shrinking branch sets high = mid — not mid - 1, because mid itself might be the answer — and low = mid + 1 on the other side. Mixing the two forms is the source of most off-by-one and infinite-loop bugs; if high = mid ever appears together with while (low <= high), the loop can hang when high equals low.

8. 8.How do you search in a sorted 2D matrix?

   It depends on how it is sorted, and interviewers use the two cases to see whether you read the problem. If every row is sorted and each row starts after the previous row ends, the matrix is a sorted 1D array in disguise: binary search over indices 0 to m × n - 1, mapping index i to a[i / n][i % n], in O(log(m × n)). If instead rows and columns are each sorted but rows overlap in range, start at the top-right corner: move left when the current value is too big, down when it is too small. Each step discards a row or a column, giving O(m + n). Binary search alone does not work in the second case, because the halves are not ordered relative to each other.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on searching (binary search & variants) and 60 across DSA.