Nuances of Binary Search
Binary Search is the algorithm to use when searching a sorted array. It's running time is in the worst case O(logN). This is much faster than a Sequential Search algorithm, which runs in O(N) time.
To demonstrate how much faster Binary Search is, consider an input size of 10 <sup>9</sup> or 1 billion.
Binary Search: O(log <sub>2</sub>10 <sup>9</sup>) = 30 Sequential Search: O(10 <sup>9</sup>) = 10 <sup>9</sup>
Binary Search can find the answer in 30 operations of an input size of 1 billion, and if the input size increased to 2 billion, we would only need one more operation. So I've proved to you it is probably worth learning Binary Search, but how does it work?
The Basic Idea
The reason Binary Search is so fast, is because with each operation, we are able to reduce the input size in half. We check the middle element and we know based on some condition, whether to continue on checking the left subarray or the right subarray. Eventually, we find the target, or reduce the array to a single element and determine the target does not exist in the array.
Implementation
Binary Search can be implemented both recursively, and iteratively. We will focus on iterative approaches.
The first thing we need to do is create two pointers, lo and hi. These represent an inclusive range of indexes where target may be.
def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1
Next, we begin the loop. The loop should run until the lo and hi pointers converge, which would indicate our input was reduced to size 1. Inside the loop, we will define what the middle index is. An important note when calculating mid is to subtract lo from hi first. Some implementations will use (lo + hi) // 2 but this may result in overflows with very large input sizes in some languages .
def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2
Now we have to decide whether we have found target, or if not, which subarray so we check next. if the index at our variable mid equals the target, then we found the index and we can return it. If not we have to decide to go left, or go right. If the the index of mid is greater than target, go left else, go right
def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid if nums[mid] > target: hi = mid - 1 else: lo = mid + 1
If the index at mid is not target, we always exclude mid from the next subarray. If we don't, there are cases which would cause an infinite loop. Consider: nums = [1,2], target = 2. In this case, mid would be 0 + (1 - 0) // 2 or 0. nums[0] would be less than our target, so we would need to exclude 0 from the inclusive range of possible indexes. If we ever break out of this loop without returning mid, we know the number does not exist in the array. We can return something to indicate target does not exist in the array, commonly -1. def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid if nums[mid] > target: hi = mid - 1 else: lo = mid + 1 return -1
Other Use Cases
First Occurrence
The function we wrote above would return mid the first time it sees a number that equals target. But what if we want to find the first occurrence of a number in a sorted array with duplicate numbers. How can we adjust our function to fit this case?
We know we cannot return mid as soon as nums[mid] == target. How would we know whether to use the left subarray or the right subarray? There are two possibilities for mid. Either it is the first occurrence, or it is after the first occurrence, but we know for sure it cannot be before the first occurrence. So we know we only need to check the left subarray! One more thing to consider is that mid could be the first occurrence, so we cannot throw away that index from inclusive range of possibilities. We would need to change hi = mid - 1 to hi = mid.
def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] >= target: hi = mid else: lo = mid + 1 return -1
Now we've introduced a new problem. Consider nums = [2], target = 2. lo, hi are both equal to 0, so we enter the loop. Then mid also gets calculated to 0. nums[mid] equals target so we enter into the if branch, which does not update either lo or hi. lo, hi are both equal to 0, so we enter the loop. Then mid also gets calculated to 0. nums[mid] equals target so we enter into the if branch, which does not update either lo or hi. lo, hi are both equal to 0, so we enter the loop. Then mid also gets calculated to 0. nums[mid] equals target so we enter into the if branch, which does not update either lo or hi. Ooops! we were stuck in an infinite loop we can fix this by changing the loop condition from lo <= hi to just lo < hi. In the case of nums = [2], target = 2, we wouldn't even enter the loop at all.
We never return from inside the loop anymore, so we have to fix our return statement outside of the loop. We know lo and hi have converged on the same index. We can check nums at that index, and if it equals target we can return lo or hi, it doesn't matter. If not we can return -1.
def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] >= target: hi = mid else: lo = mid + 1 return lo if nums[lo] == target else -1
Last Occurrence
What if we want to find the last occurrence of a number in an array of sorted numbers with duplicates? It is similar to the implementation to find the first occurrence. nums[mid] == target the two possibilities are that mid is the last occurrence or the last occurrence is after mid, but never before it. So we can throw away the left subarray if nums[mid] <= target. But just as hi was a possible answer before, now lo is a possible answer, so we cannot increment lo. Let's decrement hi in the else block instead. def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] <= target: lo = mid else: hi = mid - 1 return lo if nums[lo] == target else -1
We're finished now right? Actually this change introduced a new bug. Consider: nums = [1,1] target = 1. lo equals 0 and hi equals 1. We enter the loop because lo is less than hi. mid gets calculated to 0 therefore nums[mid] equals target. We enter the if branch and lo gets set to mid which is 0. So lo didn't get updated. We have another infinite loop.
The way to fix this, is to change the way that mid is calculated. Up until now, mid was always calculated to be the exact middle element if there is an odd number of elements, or the left middle element if there is an even number of elements. In our failing case, there are only 2 elements left and they are both equal to target. But if mid always becomes the left element, we will never increase lo to break the loop. We can adjust the calculation for mid so that we always get the right middle element. Simply change mid calculation to mid = lo + (hi - lo) // 2 + 1. This is known as bisecting right, and the previous way was bisecting left.
This is our final answer
def BinarySearch(nums, target): lo, hi = 0, len(nums) - 1 while lo < hi: mid = lo + (hi - lo) // 2 + 1 if nums[mid] <= target: lo = mid else: hi = mid - 1 return lo if nums[lo] == target else -1