Binary Search and The Fake Coin Puzzle
Algorithmically Speaking - #10: What most people know about binary search, the true power of mastering it, and an interesting puzzle for your brain.
Hello there, and welcome to a new edition of Algorithmically Speaking!
Today we are going to be talking about binary search. I know you probably know about it already, butā¦ do you?
Iāve met several software engineers working on some of the best companies in the world that still donāt know how to use binary search properly.
Believe it or not, most people think that the only application of binary search is to look for an element on a sorted array. And, while that might be one of the most used applications, it is certainly not the only one.
Stick around to discover why binary search is important and learn how to use it in the most general case. Hereās what we will cover today:
š§ What Most People Know About Binary Search ā an introduction to the most common use of binary search.
ā The True Power of Binary Search ā a comprehensive guide to when and how to apply binary search beyond its most common use case.
š° A Puzzle with Coins ā a programming puzzle for you to apply what you learn today.
Before we begin, I would like you to know that this post is a collaboration with
.I was impressed by how closely related the topics that Kanaye and I write about are. We share a passion for explaining algorithmic topics in Computer Science suitable for both the knowledgeable in the field and the absolute novice.
It feels like we both like the topic just because of how beautiful it is, let alone its multiple applications in modern technology.
If you havenāt yet, do yourself a favor and read Kanayeās work on his Substack publication.
Letās get started!
š§ What Most People Know About Binary Search
Take anyone who works as a software engineer and ask him what binary search is. Chances are they will answer that it is an algorithm that allows you to efficiently determine if an element is present or not in a sorted array.
And it is, to some extent. Binary search does allow you to take advantage of keeping things ordered and it will reward you whenever you need to search for something.
It is kind of similar to what would happen in real life. Right?
Messy room, you cannot find anything. Tidy room and everything is within reach. And yes, I know about the āmy mess is how I keep things organizedā type of people.
Letās see the most classic example of the binary search algorithm.
Take a look at the image below š
What you see is an array of integer numbers. Now, letās say we need to have the computer find out if a given number X is present in this array.
The most obvious way to tell a computer to look for an element in this array is to have it look at every element from left to right, and stop as soon as it finds the one we are looking for.
Of course, it can be the case that the element does not exist, in which case the computer checks every integer in the array and tells us that none of them is equal to X.
As you might have noticed, this algorithm behaves very differently depending on the array of integers and the number X we supply to it. If we are fortunate enough to have the element we are looking for closer to the left of the array, then the algorithm will finish in fewer steps than if the element was closer to the right end of the array or not present at all.
Letās say we want to know if the number 1
is present in the array. Then it would take the algorithm only two steps (checking the first and second numbers) to tell us that the number 1
is indeed present.
On the other hand, if we want to know if number 3
belongs to this array, then it will take the algorithm nine steps to effectively report that there is an element with value 3
.
In computer science, we determine how āgoodā an algorithm is by analyzing how it behaves in the āworstā case. For our particular problem, it is not hard to see that the worst case is when the element we are looking for does not appear in the array at all.
When this happens, our algorithm checks for every element before reporting that none of them is equal to X.
And you might think thatās ok, but it is not. Searching is one of the fundamental areas of computer science and people have been developing ways to search faster and smarter since the last century.
And the main reason is that you rarely search for something just one time, do you?
Normally, you search for things regularly (a pen, a glass of water, your phoneā¦). In computer science, most algorithms are built in a way that searching for particular elements in different collections is just something you take for granted at this point.
But enough from that.
Letās see this binary search algorithm in action and find out what is its most common application. The only one that most people know.
As I said before, binary search takes advantage of the fact that the elements have some sort of order. So, letās take our original array and sort the elements from lowest to highest.
How can we use this to our advantage whenever we need to search for any integer now?
I will illustrate a different method for searching now that we know the elements are sorted. This method is, of course, the binary search algorithm, and it is based on answering the following three questions:
What happens when we are looking at an element equal to X?
What happens when we are looking at an element smaller than X?
What happens when we are looking at an element greater than X?
The answers to these questions, in order, are:
We found X. The algorithm ends.
Every number to the left of the element we are looking at is also smaller than X.
Every number to the right of the element we are looking at is also greater than X.
These three answers define the very essence of how you use binary search to look for an element in a sorted array.
Letās see an example of how it works when we are trying to find out if the number 4
is present in the array:
In the first step, we are looking for the number 4
in the whole array, and we are going to guess that it is present in the middle of the array.
This is an illustration of how things look like at the moment:
As we can see, the number located at the position we guessed is 2
, which is smaller than the number we are searching for. So, because the array is sorted from lowest to highest, every number to the left of the 2
we are looking at is also smaller than the number we are searching for.
What this means is that we can discard the left part of the array entirely from our search space, since we know for sure there will be no number with a value larger than 2
and we are interested in number 4
.
This also means that next time, our guess should be on the right side of the element that we guessed this time. And, why not, letās guess the middle element again:
Well, now we were unlucky in a different way. It turns out that our guess this time is larger than the number we are searching for, which in turn means that every element to its right will also be larger and we discard them without problem, reducing our search space once more.
Iām sure you have realized already what is going to happen from now on. We are converging to the position where the number 4
is located and we are doing so by discarding half of the unseen elements of the array in each step.
Iām sure you notice now that I did not choose to check the middle element each time randomly.
Long story short, choosing the middle element to compare to X at each step makes you converge faster to the position where X is located or determine that it is not present at all. By discarding roughly half of the elements each time, the algorithm will take around log(n)
steps to finish, given that n
is the size of the array.
It might not seem much of an improvement when you look at an array of size 10, like the one we used for this example, but when the size becomes significantly larger, it will make a difference for sure.
And yes, this is what most people think binary search is. As I said before, an algorithm that allows you to efficiently determine if an element is present or not in a sorted array.
Hereās a great post by
diving deeper into why this is one of the most important algorithms ever devised:But there is much more to binary search than just looking for an element in a sorted array. It turns out this is just a very specific application of binary search as a whole problem-solving technique.
Letās discover how to identify binary search in the most unimaginable scenarios.
ā The True Power of Binary Search
We need to define boolean predicates to understand the true power of binary search. We can think of predicates as functions that return a boolean value, typically true or false.
Predicates are often used to make decisions in code, such as filtering elements in a collection, validating input, or controlling the flow of a program.
Binary search becomes very powerful once we stop considering just arrays and move on to more general cases in combination with boolean predicates. Consider the following question:
A building has 100 floors. You have 7 identical eggs. For an egg to break, it needs to be dropped from a minimum height. You can go to any level in the building and drop one egg to see if it breaks. Your job is to determine, by dropping eggs from different floors and checking if they break or not, what is the highest floor in the building that you can drop an egg from without breaking it. Note that each egg can only be used once since youāre too lazy to go back down to retrieve eggs that fall but donāt break, hence you must find the answer within 7 tries. How do you do it?
This example is purely theoretical but it will serve well to explain the extensions of binary search applications. Here we donāt have an array, and weāre not searching for any specific number. Instead, we use the power of boolean predicates to solve this using binary search. Hereās how:
The answer to a boolean predicate is always either true or false. In this case, we can define a predicate motivated by the following question: Will an egg break if dropped from this floor? Suppose that the highest floor you can drop an egg from without breaking it is h
. Then the answer is false for floors 0
through h
, and true for floors h+1
through 100
.
The problem now resorts to finding the largest floor number such that the value of the predicate is false. So we use binary search.Ā
At first, we know that our answer lies in the range
[0, 100]
. Guessh=50
.ĀIf the egg breaks, we know that our answer must lie in the range
[0, 49]
. Otherwise, the answer lies in the range[50, 100]
.ĀRepeat the process with the new range. For example, if the egg does not break, guess
h = 75
. Otherwise, guessh = 25
.ĀEvery time we narrow down our range of possible answers by half. We then guess
h
to be in the middle of this range, and repeat the process.Ā
This is why binary search is so strong. You can use it not just for searching for an element in an array, but for searching for the validity of a binary-searchable boolean predicate for any value in any one-dimensional search space.
A binary-searchable predicate is one where we know that the search space is divided into exactly 2 parts, one where the answer to our predicate is always false and another one where it is always true, or vice versa.
So, more specifically, binary search can be used to efficiently find the last value where a binary-searchable predicate holds or the first value where it doesnāt in your search space.
This more general use of binary search can be used in our original problem of finding a number in a sorted array simply by defining a boolean predicate that answers the question: is x
greater than or equal to the value we want to find? And we find the first value of the array that holds to this preposition.
š° A Puzzle With Coins
There are 100000 piles of stones in front of you. Every stone has the same weight, exactly 1 kg. But one stone somewhere is fake ā it weighs 2 kg. You can ask up to 30 questions. In each question, you can choose any number of piles and ask the total weight of the stones in all those piles. Can you find the pile with the fake coin?
The solution will be posted soon in
ās Substack, so make sure you subscribe to it so you donāt miss it. Until then, go ahead and try your hand at the problem here.And thatās it for today! If you are finding this newsletter valuable, consider doing any of these:
1) āļø Subscribe to the newsletterĀ ā if you arenāt already, consider becoming a free or paid subscriber.
2) š Make a one-off contribution ā thanks to all of you who have contributed to support my writing. If you feel like you are not ready for a paid subscription yet, consider leaving a one-off contribution if you enjoyed this post.
3)Ā š»Ā Read with your friendsĀ ā this newsletter grows because of readers sharing. I donāt use social media too much to advertise my writing. Iām counting on you!
Have a great day! āļø
Alberto
Solution to the fake coin puzzle is out now!
https://open.substack.com/pub/kanaye/p/solving-coin-puzzles?r=28yydd&utm_campaign=post&utm_medium=web&showWelcomeOnShare=true
Great post!