Binary Search Variants
Okay so you've got basic binary search down. But what if you need to find the FIRST occurrence of a value? Or the LAST occurrence? Or the closest value if the exact one doesn't exist? These are real-world problems that basic binary search can't solve directly. That's where variants come in.
The key insight is that standard binary search stops as soon as it finds a match. But what if there are duplicates? What if the target appears multiple times? We need to modify our approach to keep searching even after finding a match. It's like being thorough instead of lazy.
These variants are super useful in practice. Finding first/last occurrence helps with range queries. Finding nearest value helps with approximation problems. And searching in rotated arrays? That's a favorite in coding interviews.
Common Variants
For finding first occurrence, when you find the target, don't stop! Store that position and keep searching in the left half. You might find an earlier occurrence. Same logic for last occurrence but search right. Finding nearest value? Keep track of the closest value you've seen and update it whenever you find something closer.
Rotated array search is trickier. A rotated array is like [4,5,6,7,0,1,2] - sorted but rotated at some point. You need to figure out which half is sorted and decide which way to search. It's like a normal binary search with an extra twist.
function findFirst(arr, target) {
let left = 0, right = arr.length - 1, result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1;
} else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}
const data = [1, 2, 2, 2, 3, 4, 5];
console.log(findFirst(data, 2));