Binary Search or ‘Phone Book Method’

Hi guys! Today I have decided to write about binary search.

As opposed to linear search, binary search is much more efficient because it cuts your array in half every time it doesn’t find what you are looking for. It is important to remember that it can only be performed on a sorted array. To give you a better understanding of what binary search is, I’m going to provide a linear search example first, and then a binary search solution.

const search = (val, arr) => {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === val) {
      return i
    } 
  }
  return -1
}
const arr = [1,2,3,4,5,6,7,8]
console.log(search(7, arr))

Here is the question- how many iterations did it take our function to find the value? Let’s find out. Let’s console.log i on every iteration

const search = (val, arr) => {
  for(let i = 0; i < arr.length; i++) {
    console.log(i)
    if(arr[i] === val) {
      return i
    } 
  }
  return -1
}
...

In the console we get

0
1
2
3
4
5
6
6

So, for our function to find out if the number we are looking for is in the array, it took 7 iterations.

What if we are looking for the number 10? Just to remind you what our array looks like

const arr = [1,2,3,4,5,6,7,8]

Our function would have to go through every single element in the array just to return -1, because our function would not find it. And imagine if our array were 1000 items long. It would take a way too much work not to find number 1001. So we definitely need a better approach here.

Binary search is much more efficient because, every time the function runs, it cuts the array in half and tries to determine if our value is in the left half or in the right half. And again, that will only work if the array is sorted. First, let’s check if our value equals the middle index of the array, and if so, we will return the middle index

const binary = (val, arr) => {
  let lower = 0
  let upper = arr.length - 1
  
  while(lower < upper) {
    let middleIndex = lower + Math.floor((upper - lower) / 2 
    if(val === arr[middleIndex]) {
      return middleIndex
    }
    
  return -1
} 

Now let get to the actual binary search

const binary = (val, arr) => {
  let lower = 0
  let upper = arr.length - 1
  
  while(lower < upper) {
    let middleIndex = lower + Math.floor((upper - lower) / 2 
    if(val === arr[middleIndex]) {
      return middleIndex
    }
    
    if(value < arr[middleIndex]) {
      upper = middle - 1
    } else {
      lower = middle + 1
    }}
  return -1
}
console.log(binary(7, arr))

When we run the function, we get back 6. But that’s not very useful. Let’s console.log the word ‘try’ every time an iteration happens

const binary = (val, arr) => {
  let lower = 0
  let upper = arr.length - 1
  
  while(lower < upper) {
    console.log("try")
    let middleIndex = lower + Math.floor((upper - lower) / 2 
    if(val === arr[middleIndex]) {
      return middleIndex
    }
    
    if(value < arr[middleIndex]) {
      upper = middle - 1
    } else {
      lower = middle + 1
    }
  }
  return -1
}
console.log(binary(7, arr))

We get

try
try
try
try
6

So, with 7, it took us 4 iterations to find the index of 7 (in the old approach it took us 7 iterations).

How cool is that?

And as far as I know, this algorithm is a common white board interview challenge :-)

Happy coding!