JavaScript Algorithms: Binary Search

New Courses Coming Soon

Join the waiting lists

Binary search assumes the array (or any other data structure) you are searching in is ordered.

We start with the array, and the item we need to search for.

We look at the middle of the array. We take the number of elements, and we divide it by 2. Imagine we have a part of the array on the left, and the other part on the right.

If the item we have is lower than the one we’re looking for, then it must be in the right part, so we can completely discard the part on the right.

Then we perform the same action, dividing the right part of the array in 2, looking at the middle item, and we throw away part of the array.

In the end, you will get the item (or you will return `null` if the item is not found).

In the end, if the array had 8 items, we find the item in at most 4 steps.

If the array had 32 items, we have a maximum of 6 steps in the worst case. Compared to 32 in linear search, that’s a huge optimization!

Binary search has `O(log n)` complexity.

Here’s a possible implementation of it:

``````const binarySearch = (list, item) => {
let low = 0
let high = list.length - 1

while (low <= high) {
const mid = Math.floor((low + high) / 2)
const guess = list[mid]

if (guess === item) {
return mid
}

if (guess > item) {
high = mid - 1
} else {
low = mid + 1
}
}

}
``````

How does this work? We get the `list` array, and the item value we’re looking for. Then we initialize the `low` value at 0 initially, and the `high` value to the last index in the list. We first look at the middle item, and if it’s what we’re looking for we return it, and we’re done. If not, we set the `low` or `high` values to only look at the left or right part of the array, and we repeat the process until we find the item.

We return the index of the item in the array:

``````console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4
``````

We return `null` if the element is not found:

``````console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null
``````
→ Get my JavaScript Beginner's Handbook
→ Read my JavaScript Tutorials on The Valley of Code
→ Read my TypeScript Tutorial on The Valley of Code