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 midpoint. '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 midpoint: 'F'. 'A' becomes our leftmost letter and 'L' our rightmost 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 midpoint now becomes 'I'. Our leftmost letter is now 'G' and the rightmost 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 midpoint now becomes 'K'. Our leftmost letter is now 'J' and our rightmost 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 leftmost letter and rightmost 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, leftmost and rightmost 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 leftmost 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 rightmost 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 leftmost and rightmost points. Now we need to find our midpoint.
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 leftmost and rightmost 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 midpoint
let midPoint = (leftMost  rightMost) / 2
 If we are lucky and our midpoint 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 leftmost pointer:
if (arr[midPoint] < numberWeWant) {
let leftMost = midPoint + 1
}
 Else, the number we want (37) is less than the middle, we update the rightmost 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
}
}
Top comments (2)
So this algorithm can be used with the sorted array only? What happens if the array is [3, 31, 2, 23, 1, 40]
Hey, hi! Yes, you can only use this algorithm if the array is sorted.
I'll explain using your array as an example:
Say you have [3, 31, 2, 23, 1, 40], and you're trying to find the number 31. Say, too, that the midpoint is 2 (or even 23, in this case).
In its very first step, the algorithm would ignore everything that's to left of 2, since 31 is higher than 2.
That means that we would end up with:
[2, 23, 1, 40].
Now, it's impossible to find 31.