Binary Search
Intuition
Binary search is an efficient array search algorithm. It works by narrowing down the search range by half each time. If you have looked up a word in a physical dictionary, then you've already used binary search in real life. Let's look at a simple example:
Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index.
The key observation here is that the array is sorted. Let's say we pick a random element in the array and compare it to the target.
- If we happen to pick the element that equals to the target (how lucky!), then bingo we don't need to do any more work, just return its index.
- If the element is smaller than the target, then we know the target cannot be found in the section to the left of the current element since everything to the left is even smaller. So we discard the current element and everything on the left from the search range.
- If the element is larger than the target, then we know the target cannot be found in the section to the right of the current element since everything to the right is even larger. So we discard the current element and everything on the right from the search range.
We repeat this process until we find the target. Instead of picking a random element, we always pick the middle element in the current search range. This way we can discard half of the options and shrink the search range by half each time. This gives us O(log(N))
runtime.
Try it yourself
Implementation
The search range is represented by the left
and right
indices that start from both ends of the array and move towards each other as we search. When we move the index, we discard elements and shrink the search range.
1 | 1 |
| |
2 | 2 | ||
3 | 3 |
| |
4 | - |
| |
4 | + |
| |
5 | + |
| |
6 | + |
| |
7 | + |
| |
8 | + |
| |
9 | + |
| |
10 | + |
| |
11 | + |
| |
12 | + |
| |
13 | + |
| |
14 | + |
| |
15 | + |
| |
16 | + |
| |
17 | + | ||
5 | 18 |
| |
6 | 19 |
| |
7 | 20 |
| |
8 | 21 |
|
Calculating mid
Note that when calculating mid
, if the number of elements is even, there are two elements in the middle. We normally follow the convention of picking the first one, which is equivalent to doing integer division (left + right) / 2
.
Deducing binary search
It's important to understand and be able to deduce the algorithm yourself instead of memorizing it. In a real interview, interviewers may ask you additional questions to test your understanding, so simply memorizing the algorithm may not be enough to convince the interviewer.
Key elements in writing a correct binary search:
1. When to terminate the loop
Make sure while
loop has equality comparison. Otherwise, for the edge case of a one-element array, we'd skip the loop and miss the potential match.
2. Whether/how to update left
and right
boundary in the if
conditions
Consider which side to discard. If arr[mid]
is already smaller than the target
, then we should discard everything on the left by making left = mid + 1
.
3. Should I discard the current element?
For vanilla binary search, we can discard it since it can't be the final answer if it is not equal to the target. There might be situations where you would want to think twice before discarding the current element. We'll discuss this in the next module.
When to use binary search
Interestingly, binary search works beyond sorted arrays. You can use binary search whenever you can make a binary decision to shrink the search range. We will see this in the following modules.