Finding a word in a dictionary: open in the middle, see if your word is before or after, and repeat in that half.
Clues that point here
→ Sorted array (even if rotated)
→ "Find the first/last position"
→ O(log n) required
→ Search in a monotonic sequence
Not this pattern when
✕ The data isn't sorted and can't be (use a hash map)
✕ You need every match, not one position
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Binary Search on an Index · template
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids int overflow
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;