Hello!
Welcome to yet another week of Algorithms as explained to a five year old. I had initially planned to talk about A* search today but opted to go with Binary search since it is easier and more applicable in interviews (and daily work).
In a previous episode, we talked about Uninformed Search:BFS, DFS (IDS and DLS). That should have given us an idea of what search algorithms aim to achieve; finding or looking for something as efficiently as they can. In essence, they are called search algorithms because they help you search for whatever you are looking for.
This newsletter will be a bit different from previous ones, to make up for not writing last week, I will be solving and explaining a problem from leetcode that applies Binary Search. For those who do not know, leetcode is a platform for practicing algorithms for the purpose of technical interviews. I totally recommend.
Let’s get started!
Binary Search
When you hear the word “Binary” what do you think? 0s and 1s? Just two options?
Let’s look at an example before we dive in to the technical details.
Here’s a picture of where I live (I don’t actually live here). As my very good friend who just got in to town, you are looking to hangout with me. Question is, if I told you my house number, and all the houses were ordered by their numbers, how would you find me?
If the houses go from 1 to x, where x is an unknown number, how will you find my house, numbered 1067? What if my house was 1000098? What if my house is number 1?
Let me guess, you will start looking from house number 1? It is the easiest most intuitive thing to do, start from number 1, and walk upwards. Eventually, you’ll get to my house. Eventually. If my house towards the end of the housing estate, you would have visited a lot of wrong houses. On the bright side, you would have met a lot of new people too :-)
How else can we find my house?
If you were with someone else, perhaps you would apply two pointer algorithm and ask your friend to start from the end while you start from the beginning. Eventually one of you would find my house. Yay!
What if my house is at the centre of the housing estate? You and your friend would have gone through all the houses before and after my house. So much energy expanded in looking for me.
What to do? Binary Search?
Given that the houses are sorted, Binary search will excel at finding my house. Binary search suggests that when looking for an item in a sorted list (search space), start from the middle, compare the item at the middle with what you are searching for, and then decide which part of the list is important, discard the rest.
For our example, this means you can find me more efficiently if you started your search from x/2 i.e the centre of the housing estate. If the house at the centre is higher than mine, then you know for a fact that my house is on the left side thus no need looking for me on the right side. Once you have decided that I am on the left side, you look at the middle again (only considering the left side) to see if that is my house, higher, or lower than my house. If it is lower, you know that my house is on the right side and proceed to only look for me on the right. We repeat this until my house is found.
How is this better than looking for me starting from the beginning? Or even looking from the beginning and the end at the same time? Well, if my housing estate had five (5) million houses, Binary search would not bother looking at 2.5 million houses on its first attempt. In the next iteration, it would not look at half of that, so on and so forth. By halving the search area by half each time, Binary search finds the target value very quickly, even in large data sets.
Binary Search Big O
Binary Search is a search algorithm that reduces the search space by half each time it looks for the target value. However, for binary search to work, your search space must be sorted in some order (ascending or descending). This singular requirement does tend to complicate (worsen) the runtime or Big O of our solution if the search space is not sorted.
Binary search has a worst case runtime of O(logn) and a best case of O(1). O(logn) when the value being searched for is at either end of the search space and O(1) when the value being searched for is at the centre of the search space.
Application - First Bad Commit
As previously stated, binary search is very useful in searching for an item in a sorted list, to show this, we will implement Binary Search in searching for the first bad commit in a list of commits.
Given a list of commits, represented by G (good) and B(bad), determine the first index of the first bad commit represented by B. Every commit after the first bad commit is considered a bad commit.
Commits = [G, G, G, G, G, G, G, G, G, B, B, B, B, B)
What is the index of the first bad commit?
A linear search algorithm would start from either ends of the list and compare every character to see if it is a good or bad commit and act accordingly. This will end up in an O(n) outcome. The code for that would be something like:
const firstBadCommit = (commits) => {
for (let i =0; i<commits.length; i++) {
if (commits[i] === 'B') {
return i
}
}
return -1
}
If we had 1 million commits, and the first bad commit is commit 999,901, we would have gone through the first 990,900 elements. Works, but not good enough.
Using Binary search, we will have:
const firstBadCommit = (commits) => {
let end = commits.length-1
let start = 0
while (start <= end) {
let mid = Math.floor((start+end)/2)
if(commits[mid] === 'B' && commits[mid-1] === 'G') {
return mid
}else {
if (commits[mid] === 'B') {
end = mid
}else {
start = mid + 1
}
}
}
return -1
}
With Binary search, we
Start at the middle and compare if we are looking at the first bad commit. If we are, return the middle index. If not:
We check if we are looking at a bad commit, if so, our first bad commit is on the left side so we move our end to the middle. If it is not a bad commit then:
We move the start to the middle, thus we are only looking at the right side of the list.
With each iteration, we see that we cut our list down by half, thus we can use this to search a list of commits as high as a billion and still have a good performance.
Conclusion
Binary search has a wide range of applications. Its performance gain on sorted lists is amazing thus a very good algorithm to keep in mind. Problems that require Binary search are mostly search related, but more definite if the provided data is sorted. If it isn’t, one approach is always to ask to sort the list. Although this comes at a price, O(nlogn), it can be a major improvement over a non-linear approach.
Thank you so much for reading. Looking forward to next week!
Some Book Keeping
I realise that I have been writing these newsletters in no particular order, thus the topics so far have been random. I am now considering covering search and sort algorithms over the next couple of newsletters. Some newsletters will be dedicated to people preparing for interviews or just practicing algorithms. Those will cover a question from leetcode, explanations on how I solved them or how to solve them. This may be available to only paid subscribers. Please subscribe if you want to be a part of the people getting those newsletters. Also feel free to let me know what problems you’d like me to cover.