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 the target must be in the right part, so we discard the left part.

Then we perform the same action, dividing the remaining part in half, looking at the middle item, and discarding the other half.

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

  return null //if not found
}

How does this work? We get the list array, and the item value we’re looking for. We initialize low to 0 and high to the last index in the list. We 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

Lessons in this unit:

0:	Introduction
1:	Linear Search
2:	▶︎ Binary Search
3:	Bubble Sort
4:	Selection Sort
5:	Merge Sort
6:	Quicksort
7:	Algorithm Complexity and Big O Notation