Binary Search

Using splitting method to search a value in an ordered collection or array, Binary Search is a the most fundamental and useful algorithms

Details Comments (0)

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