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 letleft = 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 returnnums[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