
Using splitting method to search a value in an ordered collection or array, Binary Search is a the most fundamental and useful algorithms in Computer Science.
Background
To find a target in an ordered collection, we can split that collection into two search spaces indicated by left, mid, right indices and compare the target with the mid element. If target = mid element => return. If target < mid, keep the left-mid space for the next split, otherwise, if target > mid, keep the mid-right space for the next split. Operating the splits until target = mid or our search spaces are empty.
If a problem asks for finding / searching something in a sorted / partly-sorted collection within O(log n) time complexity, that’s a sense of using Binary Search algorithm. You can try to solve Binary Search problem to become familiar with the code structure of this kind of problem.
Template
Here is the code for the Binary Search problem problem:
var search = function(nums, target) { // pre-processing, ex: sort array if need // ... // initialize search space let left = 0, right = nums.length - 1, mid = null; // termination condition while (left < right) { // in-loop-processing // ... // calculate mid mid = left + Math.floor((right - left + 1) / 2); // select search space if (target < nums[mid]) { // exclude mid because target is // impossible in mid or above right = mid - 1; } else { left = mid; } } // left == right // post-processing return nums[left] == target ? left : -1 };
There are 5 main parts in a code for every binary search problems:
- initialize search space: set left and right to form a search space which covers ALL cases / candidates / possible elements
- termination condition: use left < right then at the end: left == right so we don’t have to think about the what variable will be used for our post-processing
- calculate mid: use mid = left + Math.floor((right – left + 1) / 2) to avoid overflow and mid is always higher than left so we will never get infinite loop in case the search space has only 2 or lower number of elements.
- select search space: reduce our search space to the space that includes the target. I usually use right = mid -1 (if mid is definitely not the target) OR left = mid (if mid may be the target). In some cases, if you want to change this, you need to change the calculation and termination condition as well to avoid infinite loops
- post-processing: we process our left to return the result as the requirements of the problem
Practices
- Sqrt(x)
- Guess Number Higher or Lower
- Search for Rotated Sorted Array
- First Bad Version
- Find Peak Element
- Search for a Range
- Find K Closest Elements
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Intersection of Two Arrays
- Intersection of Two Arrays II
- Two Sum II – Input Array is Sorted
- Find the Duplicate Number
- Median of Two Sorted Array
- Find K-th Smallest Pair Distance + EXPLANATION
- Split Array Largest Sum + EXPLANATION