Binary Search works on sorted arrays by comparing the target to the middle element. If the target is smaller, the right half is discarded; if larger, the left half is discarded. Each comparison halves the remaining search space, giving O(log n) performance — searching 1 billion elements takes at most 30 comparisons.
int binarySearch(vector<int>& arr, int target) {
int lo = 0, hi = arr.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Binary Search requires the array to be sorted. If the data is unsorted, sorting it first (O(n log n)) is only worthwhile if many searches will follow.
By comparing the target to the midpoint, we eliminate half the remaining candidates in one comparison. After k comparisons, at most n/2^k elements remain. For n=10^9, k=30 comparisons suffice.
Computing mid as (lo+hi)/2 can overflow for large indices. The safe formula is lo + (hi-lo)/2. This is a classic interview gotcha.
Binary Search has many variants: find first occurrence, find last occurrence, find insertion point. These all use the same halving idea but adjust the boundary update logic slightly.
Binary Search requires the input to be:
What is the time complexity of Binary Search?
Binary Search can be applied to: