Binary Search
Overview
Binary Search is one of the most powerful and fundamental algorithms in Computer Science. It relies on the 'Divide and Conquer' strategy. If you are searching for a word in a dictionary, you don't read page 1, page 2, page 3 (Linear Search). You open it to the middle. If the word is alphabetically lower, you tear the book in half and throw away the right side. You repeat this until you find the word. Binary Search achieves blindingly fast O(log N) Time Complexity, but the data MUST be sorted first.
Syntax
At every step, the `mid` element is checked. If it isn't the target, we completely discard half of the array by shifting the `left` or `right` pointers.
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
// Prevent integer overflow bug!
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
left = mid + 1; // Target is in the right half
} else {
right = mid - 1; // Target is in the left half
}
}
return -1; // Target not found
}Common Pitfalls
- Running Binary Search on an unsorted array. It will return completely garbage results or infinite loops.
- Using `<` instead of `<=` in the while loop (`while(left < right)`). This causes the loop to terminate prematurely when checking the final remaining element.
Interview Tips
- Binary Search achieves O(log N) speed by cutting the search space in half repeatedly, but the data MUST be sorted first.
Real-World Example
Finding a specific Git commit that introduced a bug (Git Bisect) heavily relies on Binary Search across the commit timeline.
public int findFirstBadVersion(int n) {
int left = 1, right = n;
int firstBad = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
firstBad = mid; // Record it, but keep checking left
right = mid - 1; // Maybe an earlier version was bad too
} else {
left = mid + 1; // Bad version is further ahead
}
}
return firstBad;
}