Let’s say you are playing a game with your friend. The game is that your friend thinks of a number between 1 and 100, you have to try to guess this number, if you guess incorrectly they will tell you ‘higher’ or ‘lower’ depending on your guess. Most people would probably just say the first number that they think of and hope they luck out on hitting the correct answer, but is there a way that we can be more strategic about this?
The answer is yes. One strategy might be to just go through all of the numbers in sequence, ‘is it 1?’ ‘is it 2?’ etc. The problem is that if your friend is thinking of 98 you will be there for quite a while guessing. The best strategy for this game is to employ the Binary search algorithm.
If you make your first guess the halfway point between the two numbers, 50, whether your friend says higher or lower, you can eliminate half of the numbers. If they say lower then your next guess should be halfway between 1 and 50 — 25, or if they say higher it should be halfway between 50 and 100 — 75. Thus in just two guess you can eliminate most of the numbers. With each guess, depending on whether or not they say higher or lower, you should always determine your next guess as halfway between the remaining possibilities.
In this way you can actually calculate the maximum amount of guesses it will take you to hit the right answer. If you took the first approach, to just guess the numbers sequentially, it could take 1 guess, if they happen to think of the number 1, but it could also take 100 guesses, if they think of 100. To calculate the guesses for the Binary search algorithm strategy you can use a logarithm.
The calculation we need would be log2(100). We use log2 because we are always halving the the list, and 100 is the maximum number that we are trying to guess. If that sounds confusing, basically is it the number of times that we need to multiply 2 by itself to get 100. 2 x 2 = 4, 2 x 2 x 2 = 8, 2 x 2 x 2 x 2 = 16 and so on. Because the result doubles each time it turns out that we just need to multiply 2 by itself 7 times times to get 100. Or 27 which gets us 128.
The cool thing about this is, because the number is doubled each time you can see that if your friend were to think of a number between 1 and 200, then you would only need 8 guesses to get it. If you had a lot of time on your hands you could even get them to think of a number between 1 and 1 billion and it would only take you a maximum of 30 guesses to get it using this method. This is because the bigger the number the more numbers you eliminate when you split the list of numbers in half.
In JavaScript code the Binary search algorithm would look something like this:
const binarySearch (array, item) => {
let low = 0
let high = array.length - 1
while (low <= high) {
let mid = Math.floor((low + high) / 2)
let guess = array[mid]
if (guess === item) {
return mid
} else if (guess > item) {
high = mid - 1
} else {
low = mid + 1
}
}
return null
}
The Binary search algorithm is a great way to search through data, but it has it’s limitations. The main one being that it can only work on a list of items that is sorted in a particular order, such as alphabetical or numerical order. This is because the placement of the items is predictable in these cases. However in a list that is not sorted the method does not work!
Perhaps you can win a bet or two by telling your friend that you can guess their number in no more than 7 tries!