Understanding the binary search algorithm

#algorithms #tutorial

The binary search

Imagine you're given this big phonebook full of people's names and their respective phone numbers. Your task is to find John's phone number. What would be the easiest and fastest way to find him?

We could start from the first page and flip through each page, one by one, until we finally find John. As you might have thought, this is extremely slow and inefficient. Look at, for example, the phonebook in the image; there are thousands of pages with, possibly, hundreds of names within them. Imagine how long would it take to find John?

We can do better.

We know that this particular phonebook is alphabetically sorted. We know, therefore, that the first page shows names that start with 'A' and the last page shows names that starts with 'Z'. We don't know, however, which page starts showing names with 'J' (John's first character).

Cutting the problem in half

Odds are that if you have this phonebook on your hands, you wouldn't check each page one by one starting from the beginning. You would probably open the phonebook roughly to the middle and check which letter comes up.

Say you do open the phonebook to the middle and you end up on the 'M' session. Now, if you are looking for John, you would ignore everything that's to the right portion of the book since 'J' is smaller than 'M'.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

You see how much more efficient that is? In just one step, we cut the problem in half.

Is 'M' the letter we were looking for? No, so let's keep repeating this process until we find the session 'J':

In our first step, we chose letter 'M' as our mid-point. 'M' is not the letter we are looking for, so we can disregard it as well:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Let's choose our new mid-point: 'F'. 'A' becomes our left-most letter and 'L' our right-most letter.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
'J' is greater than 'F'; therefore, we can disregard 'F' and everything that's less than it.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Our new mid-point now becomes 'I'. Our left-most letter is now 'G' and the right-most letter is still 'L'.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
'J' is greater than 'I'; therefore, we can disregard 'I' and everything that's less than it.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Our new mid-point now becomes 'K'. Our left-most letter is now 'J' and our right-most letter is now 'L'.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
'J' is less than 'K'. We can cut 'K' and 'L', leaving 'J' by itself. Our left-most letter and right-most letter are now the same, and they both point to the letter we want: J.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

If we were to do this linearly, it would take thousands of steps. With binary search, however, we were able to find our 'J' session in just a few steps.

Converting this idea to code

Repeating the aforementioned process in your mind is easy, but a computer is logical at its core. How do we tell to a computer where is the mid, left-most and right-most point? Let's use Javascript to code this up.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]

We begin by creating a sorted array with a few numbers in it. Just like the GIF above, we wish to find the number 37.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

In the beginning, our left-most point points at the beginning of the array; the index 0.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0

And our right-most point points to the last element of the array; the array's length.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0
let rightMost = array.length - 1

Great. We already know our left-most and right-most points. Now we need to find our mid-point.

Before we do so, let's take a step back. Look at the alphabet example I gave above. We repeated the process of cutting the array in half a couple of times. We only stopped when the left-most and right-most points pointed to the same letter and the letter was the one we were looking for: J.. Maybe we need some sort of iteration?

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0
let rightMost = array.length - 1

while (leftMost <= rightMost) {
  // TODO
}

Just like the alphabet example, in each step, we do the following:

Calculate the mid-point

let midPoint = (leftMost - rightMost) / 2

If we are lucky and our mid-point is the number we want (37), then just return it.

if (array[midPoint] === numberWeWant) {
  return array[midPoint]
}

Or, if the number we want (37) is greater than the middle, we update the left-most pointer:

if (arr[midPoint] < numberWeWant) {
  let leftMost = midPoint + 1
}

Else, the number we want (37) is less than the middle, we update the right-most pointer:

if (arr[midPoint] < numberWeWant) {
  let leftMost = midPoint + 1
} else {
  let rightMost = midPoint - 1
}

Piecing it all together, we have:

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0
let rightMost = array.length - 1

while (leftMost <= rightMost) {
  let midPoint = (leftMost - rightMost) / 2

  if (array[midPoint] === numberWeWant) {
    return array[midPoint]
  } else if (array[midPoint] < numberWeWant) {
    let leftMost = midPoint + 1
  } else {
    let rightMost = midPoint - 1
  }
}