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 start, mid, end indices and compare the target with the mid element. If target = mid element => return. If target < mid, keep the start-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 letstart = 0, end = nums.length - 1, mid = null; // termination condition while (start < end) { // in-loop-processing // ... // calculate mid mid = start + Math.floor((end - start) / 2); // select search space if (target > nums[mid]) { // exclude mid because target is // impossible in mid or abovestart = mid + 1;} else {end = mid} } // start == end // post-processing returnnums[start] == target ? start : -1};

There are 5 main parts in a code for every binary search problems that you can customize:

**initialize search space**: must set*start*and*end*to form a search space which covers**ALL**cases / candidates / possible elements**termination condition**: I like to use*start < end*then at the end:*start == end*so I don’t have to think about the what variable will be used for my post-processing.**calculate mid**: I use*mid*=*start + Math.floor((end – start) / 2)*to avoid overflow and mid is always smaller than right 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*start = mid + 1 (if target > mid), OTHERWISE, start = mid.***post-processing**: we process our*start*to return the result as the requirements of the problem

## Applications

If you notice, there is no condition *target == nums[mid]* in my loop, so even *target == nums[mid]*, the loop will continue until it find:

- start =
**lowest index**that*nums[index] = target*if mid calculation is:*mid = start + Math.floor((end – end) / 2)*. I call this is “focus start” template. This is very useful to solve the problems related to counting like: Kth Smallest Element in a Sorted Matrix - start =
**highest index**that nums[index] = target if mid calculation is:*mid*=*start + Math.floor((end + 1 – start) / 2)*. I call it “focus end“. If you use this, please make sure you change the search space selection to:*start= mid + 1 (if target > the mid) AND end = mid (if target <= the mid).*

*Note: You may need to add *target == nums[mid] *in your loop in some cases (like there are too many repeating values), so just analyze your problem and make rational modifications to the template.

In the case when *the target is not in our nums*:

- the “focus start” template return
*start*right above the target:*nums[start-1] <***target**< nums[start] - the “focus end” template return
*start*right below the target:*nums[start] <***target**< nums[start+1]

## 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