Binary Search

The idea behind the binary search algorithm is to minimize search times within an array.

Typically, binary search algorithms are particularly useful when searching through a sorted array.

If we are given a sorted array and a target value, how would one find the index of the target value?

We could use a sequential search:

function regularSearch(array, target){
  for(let i = 0; i < array.length; i++){
    if (array[i] === target){
      return i
    }
  }
}

But this results in a time complexity of O(n). Could we do better?

Since we know the array is sorted, we can use that to our advantage. Say we are searching for the number 2 in [1,2,3,4,5,6]. We can compare it to the middle value of the array and further query the half that contains it.

I find this GIF particularly useful in visualizing it.

For binary searching we would use a code like this:

function binarySearch(array, target){
   
  let startIndex = 0
  let endIndex = array.length - 1
  while(startIndex <= endIndex){
    const…