Binary Search
Overview
Binary Search is one of the most powerful algorithms in computer science. If you have a sorted collection of data, you never need to check every element.
Instead of searching from the beginning, you look at the middle element. If the target is smaller than the middle, you know with absolute certainty that it cannot be in the right half. You completely discard the right half and repeat the process on the left half, continually dividing the search space by two.
This halving process means you can search 1,000 items in 10 guesses, 1 million items in 20 guesses, and 1 billion items in just 30 guesses! This is the definition of O(log N) time complexity.
The mandatory prerequisite is that the data must be sorted beforehand. If it is not sorted, the algorithm will confidently look in the wrong half and fail.
Syntax
public class BinarySearch {
// The array MUST be sorted for this to work
public static int search(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
// Find the middle. We use this formula instead of (left+right)/2
// to prevent integer overflow for massive arrays.
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Found it!
}
// If target is greater, discard the left half
if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, discard the right half
else {
right = mid - 1;
}
}
return -1; // Not found
}
}Common Pitfalls
- Integer Overflow when calculating
mid. Writingint mid = (left + right) / 2;is a famous bug. Ifleftandrightare massive numbers (near 2 billion), adding them together exceeds Java's maximum integer limit (2.14 billion), wrapping around to a negative number and causing anArrayIndexOutOfBoundsException. Always useleft + (right - left) / 2. - Infinite loops from incorrect loop conditions. Using
while (left < right)instead ofwhile (left <= right)will fail to check the final remaining element. If the target happens to be that final element, your search will incorrectly return -1. - Failing to shift past
mid. Writingleft = mid;instead ofleft = mid + 1;will cause an infinite loop because the search space will stop shrinking whenleftandrightare adjacent.
Interview Questions
Technically yes, but practically no. To find the 'middle' of a Linked List, you must traverse it, which takes O(N) time. Doing an O(N) operation at every step of an O(log N) algorithm makes the total time O(N), defeating the entire purpose of Binary Search. Binary search requires O(1) random access, which arrays provide.
It's an advanced pattern where you aren't searching a literal array. Instead, you know the answer to a problem lies in a sorted range (e.g., between 0 and 1000). You guess the middle value (500), write a helper function to test if 500 is possible, and if it is, you discard the bottom half and test 750. This turns optimization problems into 'yes/no' guessing games.
Real-World Example
Looking up a word in a physical Dictionary. You don't read page 1, page 2, page 3 (Linear Search). You open the book to the middle. If you're looking for 'Zebra' and you land on 'Monkey', you know 'Zebra' must be in the second half of the book. You ignore the entire first half and split the second half again.
// Finding a Git commit where a bug was introduced (git bisect)
int left = 0; // oldest known good commit
int right = commits.length - 1; // newest known bad commit
while (left <= right) {
int mid = left + (right - left) / 2;
if (runTests(commits[mid]) == FAILED) {
// Bug exists here, so it was introduced at this commit or earlier
firstBadCommit = mid;
right = mid - 1;
} else {
// Tests pass, bug must be introduced later
left = mid + 1;
}
}Check Your Knowledge
Test your understanding of Binary Search with these quick questions.