🙏

জয়  শ্রী  রাম

🕉

---

This chapter will give you a whole new perspective about the versatility and usages of Binary Search. It is going to be a very powerful approach, so please pay special attention throughout this chapter. Grabbing the concept discussed in this chapter by heart will enable you solve some of the super complex problems in just minutes by using Binary Search. Many of the problems that you wouldn't even have thought could be solved by Binary Search, will seem an appropriate candidate to be easily solved by Binary Search.

Basically, what we are going to learn in this can be summarized in just few sentences:

If you can convert a given problem into a problem that is about "finding the minimum value in the search space for which a certain condition satisfies", then you could be pretty sure that the given problem can be solved by Binary Search. Or I can say in a different way, Binary Search is all about "finding the minimum value in the search space for which a certain condition satisfies". As you would see later in this chapter, what is challenging while converting the given problem is to figure out what that condition should be that we need to satisfy, and the second most challenging part would be to figure out the search space. The search is a range of values, say [1, 6] which means from 1 to 6 both inclusive, that could be a potential answer and it's naturally sorted.

What I just wrote may not make sense right now, but bear with me, by the end of this chapter everything will be crystal clear to you.


If you look closely at the problems discussed below you would find that they have a pattern: in almost all the problems you are having to optimize something and find the possible minimum.

New way of Implementing Binary Search:

Binary Search is deceptively simple and most first time learners do the mistake of taking its simplicity and implementation for granted. In fact, the root of this problem is how the use case for Binary Search is posed in front of the learners. It gets ingrained in the learners' mind that Binary Search can only be used in scenarios like "Given a sorted array, find a specific value in it". While the statement is not wrong at all, it belies the potential of Binary Search in solving problems which do not directly states that it contains a sorted array and you would have to find a specific value. In fact, in most cases it's not about finding a specific value at all. It is about finding less than or equal to a value. Lack of this simple understanding even make solving the problem "Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order." seem hard even though they can easily solve "Given a sorted array and a target value, return the index if the target is found". The objective of this article to get rid of all these confusions and unleash and appreciate the power and beauty of Binary Search Technique .

Let's take a look at the below general template for how we can implement Binary Search. If you haven't read already, I would highly recommend you read the previous chapter first which concentrates on Binary Search Fundamentals.

public int binarySearch() {
    int left = min(search_space);
    int right = max(search_space);

    while (left < right) { // terminates when lo == hi
        int mid = left + ((right - left) / 2);
        if (condition(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Apart from enabling us solving some very complex problems using this approach, what other problems does this approach solve ?

We do not have to worry about the below confusions that often hinders us from writing a bug-free binary search based solution:

• When to exit the while loop ?
  Should we use left < right or left <= right in the while(...) condition ?
• How to initialize the boundary of variable left and right ?
• How to update the boundary variables depending on the mid variable ? How to choose which one is correct: left = mid or left = mid + 1, and right = mid or right = mid - 1 ?

The template I have shared above takes away all this confusion if you know how to use the template, and you will master that art by the end of this chapter.

So, how this implementation works ?

Let's talk about the search space first, because this is single most important thing in this approach, followed by determining the condition we are trying to satisfy. Search Space and Condition to satisfy go hand in hand. Depending on the problem you would have to figure out the range of values in which the answer that you are trying to find lies. This range of possible values is called Search Space. Important to say, in the template above we are keeping the search space sorted in ascending order.

The condition is the condition you are trying to satisfy in order to get your answer.

• Every time mid satisfies the condition we assign mid to the right. But just because our condition got satisfied, we don't stop there, we continue our search on the left side of the search space to see if we can get a lower value which would still satisfy the condition. We stop when left is equal to right. At any point of time right is the value (mid) that satisfies condition.
• Anytime mid does not satisfy the condition we keep the right unchanged and assign left as mid + 1. This is because we would be constructing the search space and the condition in such a way that if a mid does not satisfy the condition any value lesser than mid won't either. This may sound super difficult now, but trust me, as we would see in the examples below, they are not that hard. So, at the end we get the minimum value (mid) for which the condition is satisfied.

Since we are interested in finding MINIMUM value in the search space, we move from right to left in the search space every time we get a match , assuming the search space is sorted in ascending order. I said we move from right to left, because once we get a value in the search space that satisfies the condition, we continue searching in the lower value set of the search space (which means, more towards left) to see if we get even lower value as the minimum value that satisfies our condition. This means every time we get a match, i.e, we get a value in our search space that satisfies our condition, we contract the search space appropriately and move our search space towards left (i.e, towards lower values) by doing right = mid.

But, whenever we get a mismatch, we move towards right: left = mid + 1.

So as we see the challenging part would be to convert a problem into "find the minimum value (mid) in the search space that satisfies the condition, after you have defined the search space and the condition."
Important to notice, the above statement holds true only when the search space is sorted in ascending order.


Now before going to our examples, let's quickly go over why I think the traditional Binary Search implementation does not do a justice at showing the potential of Binary Search. It is because the traditional implementation gives the impression that the search space is the indices of the given array and mid is always one of the indices. Clearly this is not always true and the search space depends on the given problem. In fact, traditional implementation does not even let one know that there is a concept of search space ingrained in the Binary Search algorithm. Secondly, from the traditional Binary Search implementation it seems like there will always be a sorted array explicitly given in the given problem, while in some of the most complex problems that could be efficiently solved by Binary Search there is no mention of any sorted array and it is the most challenging part to figure out that the problem translate into something that involves a sorted array as the search space .


Now time to take a look at some example problems that would make all the concepts discussed above clear to you and would show how we can use the above discussed approach in solving some non-trivial problems. These problems would make the concept of determining search space and satisfying conditions, and converting a problem into a problem of finding minimum value in the search space that satisfies the condition very clear.

Problem #1:

You are an engineering lead and currently leading a team to develop a new product. Unfortunately, the latest version of your product failed the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Write and implement an algorithm to find out the first bad one, which causes all the following ones to be bad.
Assume that you already have an API bool isBadVersion(version) which will return whether version is bad. You should minimize the number of calls to the API.

Example:
Let's say n = 10.

call isBadVersion(8) -> false
call isBadVersion(9) -> true
call isBadVersion(10) -> true

Then 9 is the first bad version.

Java and Python Solution with Detailed Discussion of the Algorithm:

Login to Access Content

Problem #2:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.

Example 1:
Input: [4,5,7,8], 6
Output: 2

Example 2:
Input: [11,43,45,77], 20
Output: 1

Example 3:
Input: [11,22,44,60], 70
Output: 4

Example 4:
Input: [1,11,22,33], 0
Output: 0

Java and Python Solution with Detailed Discussion:

Login to Access Content

Problem #3:

A conveyor belt has packages that must be shipped from one port to another within D days.
The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within K days.

Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], K = 5
Output: 15
Explanation:
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:
Input: weights = [3,2,2,4,1,4], K = 3
Output: 6
Explanation:
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], K = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Java and Python Solution with Detailed Explanation of the Algorithm:

Login to Access Content

Problem #4:

Problem Statement: Honu loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.
Honu can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.
Honu likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:
Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:
Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:
Input: piles = [30,11,23,4,20], H = 6
Output: 23

Java and Python Solution with Algorithms and Detailed Explanation:

Login to Access Content

Problem #5:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.

Example 1:
Input: [3,4,5,1,2]
Output: 1

Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0

Java and Python Solution with Detailed Explanation:

Login to Access Content

Problem #6:

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

Java and Python Solutions:

Login to Access Content




There are situations when a problem cannot be converted to "finding MINIMUM value from the search space that satisfies a condition", BUT can be converted to "finding MAXIMUM value from search space that satisfies a certain condition". To know how this type of problems could be solved by Advanced Binary Search, visit Longest Repeating Substring. Enjoy!

Instructor: