Basic Searching Questions
Six warm-up exercises to lock in binary search. Each one is a direct application of the unified template — by the end you should feel comfortable identifying the monotonic predicate at a glance.
1. Find an element in a sorted array
The canonical problem. Use the template — define the predicate arr[i] >= target and the answer is “the first true index, if it points at target.”
Time: O(log n). Space: O(1).
2. Find the first occurrence of a duplicated value
Same predicate as classic search — arr[i] >= target. The template naturally returns the leftmost index because of hi = mid (we keep mid as a candidate, narrow leftward whenever possible).
3. Find the insertion position
If the target isn’t in the array, return the index where it would be inserted to keep the array sorted.
Same template — just don’t do the “did we find it?” check. Whatever lo is at the end is the insertion point.
Time: O(log n).
4. Integer Square Root
Find the largest integer s such that s² ≤ x. Binary search over the answer space [0, x] — the predicate s * s > x is monotonic (false…false…true…true).
5. Find a peak element
A “peak” is any element strictly greater than its neighbors. For arr = [1, 3, 2], the peak is 3 at index 1. The trick: binary search by comparing arr[mid] with arr[mid + 1].
6. Find minimum in a rotated sorted array
A sorted array rotated at some pivot — e.g., [4, 5, 6, 7, 0, 1, 2]. Find the minimum.
Quick check
Ready for the full interview classics? Head to Practice Questions — eight problems, all variations on the template you just drilled.