Binary search is an extremely useful and popular algorithm used for quickly searching in a sorted array. Binary search is even used by people in real life (outside of programming) when they play the *guess the number* game. One person thinks a number between 1 and 100, and the other person tries to guess. The response is only *less*, *equal* or *greater*. If you guess 50 and get a *less* response, you just narrowed down the search to half the interval, 1 to 50. You can keep going and guess 25. No matter if what answer you get, you either win, or narrow down the interval again to a half. This is how binary search works. We test our searched value against the element in the middle, if it's less than the middle element, we repeat the process on the left part, if it's greater than the middle element, we repeat the process on the right part. We repeat this until we get a value which is equal, at which point the search is complete.

The initial requirement is that the array must be sorted. Why? Because a sorted array has a simple property. If we take any two indexes `i`

and `j`

, if `i <= j`

, then `array[i] <= array[j]`

. This means if we know that the searched number is lower than the number at the middle index, its index must be also lower.

To implement to algorithm we will use two variables to store the bounds of our search area, `low`

and `high`

. We begin by setting `low = 0`

and `high = array.length`

. We calculate the middle as the average of `low`

and `high`

, always rounding down using the `Math.floor`

function. Note that we could also use a bitwise shift to the right with the `>>`

operator to achieve the same, but we'll keep the division explicit to make things easier to read. We then compare the number at the middle index to our search value. Here we can run into three different cases:

- If
`array[mid] < value`

, then we need to move to the right, updating our lower bound`low = mid + 1`

. We add the one because the value can't possibly be at`mid`

(since it's greater than`array[mid]`

), so we can skip that index entirely. - If
`array[mid] > value`

, then we need to move to the left, updating our upper bound`high = mid`

. Since we initialize our`high`

to`array.length`

, the search range does not include the`high`

index (it's a left-closed interval), which means we don't need to subtract`1`

from the upper bound. - If
`array[mid] == value`

, we simply return the`mid`

index as a result.

We keep iterating until `low == high`

, at which point the search is narrowed down to a single element which must be the result if the element was initially present.

```
function binarySearch(array, value) {
var low = 0;
var high = array.length;
while (low < high) {
var mid = Math.floor((low + high) / 2);
if (array[mid] < value) {
low = mid + 1;
} else if (array[mid] > value) {
high = mid;
} else {
return mid;
}
}
return high;
}
```

Lastly, it's important to note that **if we search for an element which is not present in our array, we still get an index as a return value**. There are two ways to think about this. Either we think of the `binarySearch`

function as searching for an index of an existing element inside the array, at which point we might want to return `-1`

in case the element isn't found. Or we use it to calculate an index at which we should insert a new element into the array so that it remains sorted.

If we wanted the first variant, we could modify the binary search to check the result value before returning it.

```
function binarySearch(array, value) {
var low = 0;
var high = array.length;
while (low < high) {
var mid = Math.floor((low + high) / 2);
if (array[mid] < value) {
low = mid + 1;
} else if (array[mid] > value) {
high = mid;
} else {
return mid;
}
}
if (array[high] == value) {
return high;
} else {
return -1;
}
}
```

Alternatively, we can use the first implementation to implement an insert into a sorted array which uses binary search to find the right place to insert the value. This is rather trivial, we simply find the proper index with the first version of our `binarySearch`

, and then use `Array.splice`

to insert the new value.

The original code is provided here again so that the example as a whole can be copy-pasted into a developer console (or any other JavaScript environment) for experimentation.

```
function binarySearch(array, value) {
var low = 0;
var high = array.length;
while (low < high) {
var mid = Math.floor((low + high) / 2);
if (array[mid] < value) {
low = mid + 1;
} else if (array[mid] > value) {
high = mid;
} else {
return mid;
}
}
return high;
}
function binaryInsert(array, value) {
var index = binarySearch(array, value);
array.splice(index, 0, value);
}
var arr = [1, 2, 3];
binaryInsert(arr, 2);
console.log(arr);
// [1, 2, 2, 3]
binaryInsert(arr, 5);
console.log(arr);
// [1, 2, 2, 3, 5]
binaryInsert(arr, 0);
console.log(arr);
// [0, 1, 2, 2, 3, 5]
```

## Time complexity

The main benefit of binary search is its time complexity, which is only \(O(\log n\), compared to regular linear search (going through the whole array searching for the right index), which is \(O(n)\). Searching `1000000`

elements using binary search would only take roughly `20`

steps while it could take up to `1000000`

steps.

But why is it \(O(\log n)\)? Each iteration of binary search reduces the search space by half, which means we can translate the question *how many steps does it take?* to *how many times can we take a half of a number until we get to 1?* If the array length was a power of two, meaning we could write it as \(2^k\), we could divide it by `2`

exactly `k`

times. If we have an arbitrary number `n`

and we want to write it as \(2^k\), we can calcualte `k`

with a logarithm, specifically \(\log_2 n = k\). But by the definition of the big-O notation, we don't need to worry about constants, and since \(\log_2 n = \frac{\log n}{\log 2}\), we can simply use \(O(\log n)\).

#### See also

- Binary Heap (Priority Queue) in JavaScript
- Few notes on the Binomial and Fibonacci heaps
- Bloom filter in JavaScript
- Bit Vector in JavaScript
- Fibonacci Numbers

#### Liked this blog post? Share it!

comments powered by Disqus