Pizza Delivery Problem
Let’s learn Binary Search with a fun problem! You do pizza delivery part-time to earn some extra bucks. Since you are a sincere and cool person, you did very well in delivery job and the manager happily announced a $100 bonus for you!
But …. with a strange condition was applied!
He said, you will go to “Pizza Road”, a special road in the city and deliver pizza to a certain house. But the house numbers in Pizza Road are not visible in-front of the house. To see the house number, you will have to press a button in the front door and then the number of house will be visible to you. All houses in that Pizza road follow this mechanism.
However, there are 100 houses in that road and houses are numbered in sorted order. But the numbers do not maintain contiguity and they are random by nature. For instance, the first house number could be 10, the second one could be 15 (which is greater than the first house number) and the third one might be 122 (greater than the second house number) and so on. In other words, the house numbers do not increase (or decrease) by 1 as you walk through. Rather they can increase (or decrease) by any random number. Below is a sample house arrangement of Pizza Road.
After explaining about Pizza Road house numbers, your manager now threw the strange condition to you! That condition is, while delivering pizza to a certain house, you will have to press the button of a house to know the house number, right? If you do not find the house you are looking for, you will naturally go to another house and press the button again. Each time you press a button to know a house number, you will lose $5 (from your bonus money) if that is not the house you are looking for!
Linear Search
Let’s reduce the problem size to make it simple to understand. Let’s say, Pizza Road has 10 houses and their numbers are stored in an array as below with indices 0 to 9:
You have to deliver pizza to house number 400 (index 7).
You started from the first house (number 10, index 0) and pressed the button to see the house number. That’s not the house you are looking for. So, you lose $5! Now you went to the second house(number 15, index 1) and pressed the button, again it’s not the house you are looking for, lost another $5 (total $10). By following this process, you finally found the house number 400 (index 7) and delivered the pizza. But you already had to check total 7 houses before finding the correct one and lost $35 (=7 * $5)!
This process of searching an element in an array by checking one adjacent element after another, is what they call Linear Search.
/*
This function will return true once you find the house to deliver pizza
*/
bool findPizzaOrderHouse(int pizzaOrderHouseNum){
int pizzaLandHouses[] = {10, 15, 122, 233, 237, 240, 356, 400, 401, 574}; // array to store house numbers
for(int i = 0; i < pizzaLandHouses.size(); i++){
//loop from the first house and continue going to the next//and so on
if(pizzaLandHouses[i] == pizzaOrderHouseNum){ //house number match with desired house number to deliver!
return true;
}
}
return false;
}The above C++ code is exactly how linear search will work for this problem. Inside the for loop, where the array element is being checked with the desired house number (pizzaOrderHouseNum), is a representation of pressing the button and check house number.
Binary Search – Intuition
Applying linear search starting from left of the road you lost $35. Can we do better?
Let’s say, instead of going from the beginning of the road, you came to the middle of the road. You don’t know house numbers but you do know how many houses are there in the road. In the smaller version of the problem, we have taken 10 houses. So, you know there are 10 houses and you can easily go to the middle house. (In case of 10, the middle indices are both 4 and 5. You can go to any one of them) Then you can know the house number of the middle house.
If the number of the middle house is greater than what you are looking for, you should not go to right side. Because, the right side house numbers will only increase. Applying the same logic, if the number of the middle house is smaller than what you are looking for, you should not go to left. This way, you will reach to the desired location much faster than linear search and incur lesser loss of money. Let’s see below how the algorithm works.
Binary Search Algorithm
The algorithm first takes the entire array as its problem space. Then it takes the left and right indices of the problem space to calculate midindex value.
If the value associated with middle index is smaller than the target number, the algorithm goes to the right. That means, it updates leftas left = mid + 1.
But if the middle index value is greater than the target number, the algorithm should go to left. That means, it will then update right as right = mid – 1
The algorithm stops either if 1) the desired value is found or 2) left >= right as the code below.
/*
This function will return true once you find the house to deliver pizza (Binary Search Version)
*/
bool findPizzaOrderHouse(int pizzaOrderHouseNum){
int pizzaLandHouses[] = {10, 15, 122, 233, 237, 240, 356, 400, 401, 574}; // array to store house numbers
int left = 0;
int right = pizzaLandHouses.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(pizzaLandHouses[mid] == pizzaOrderHouseNum)
return true;
if(pizzaLandHouses[mid] <= pizzaOrderHouseNum)
left = mid + 1;
else
right = mid - 1;
}
return false;
}You can see, applying binary search you just have to check only one house and will lose only $5! This is a dramatic improvement compared to linear search, right? But why Binary Search is so fast and how much faster it is compared to linear search? We will write a separate blog explaining this.
What you should do at this point is to practice what you have learnt. There is no better way to grasp algorithm other than solving problems related to that. Below are some problems you should try out.
Happy Coding! 😀