Let's learn about binary search and solve some problems based on it. Special thanks to leetcode (for the awesome collection of binary search problems).
This post is an outcome of rigorous reading of other blogs on leetcode and other sites (including youtube). I hope to present in best way, everything I think I know about binary search.
I am no expert and hence some mistakes are sure to happen. If you notice them, let me know in the comments.
Let's start with finding the index of a target number in an sorted array containing distinct elements. Let nums be the array and n be the array size. Also, let's assume that that target number exists in the array.
First way would be to start iterating from 0 to n-1 and return the index as soon as we encounter the element. In the worst case, we travel the whole array. Hence, the time complexity is O(n).
We can use binary search to improve the time complexity.
The whole idea of binary search is to reduce the search space by half in each iteration. We keep two variables low and high, which indicate the current search space (i.e. the range of indices where our target element might lie).
The initial search space is 0 to n-1 because any of those indexes can have the target element.
Now, in each iteration, we calculate mid = (low + high)/2.
Case 1: The element at mid (i.e. nums[mid]) is equal to target. In this case, we just return mid.
Case 2: If the element at mid is lower than target then isn't it obvious that the target exists to the right of mid ? Why? Because the array is sorted so all greater elements are towards the right. In this case, we arrange low to be mid + 1.
Case 3: Similar is the case when element at mid is greater than target. We must go left since smaller elements exist to left. So, we change high to mid - 1
We now know when to go left and when to go right. But, till when? Is there any criteria for termination? Yes.
Let me remind you that low and high basically represent the search space. In each iteration, we are sqeezing the search space to half it's current size. So, as long as there is one element in the search space, we continue our process.
So, what's the condition?
The condition is:
while (low <= high) // This ensures that there is atleast one element in search spaceLet's now take an example. All examples follow 0-based indexing.
nums = [2, 4, 5, 9, 11, 13]
target = 11Iteration 1:
low = 0, high = 5
mid = (0 + 5) / 2 = 5/2 = 2
nums[mid] = nums[2] = 5.
Since, element at mid is 5 and we looking for 11, it must exist to right. So, we now set low to mid + 1 (i.e. 3)
Iteration 2:
low = 3, high = 5
mid = (3 + 5) / 2 = 8/2 = 4
nums[mid] = nums[4] = 11
Since, element at mid is equal to target, we return mid as the answer.
I had said that the element is guaranteed to exist in the array. What if it doesn't ? In most cases, we are supposed to return -1. So, if we come out of loop, it means that element was not found in array else the function would have returned. So, we can directly return -1.
One more important caution. To find mid, we use mid = low + (high - low)/2 to prevent overflow.
The implementation is as follows:
int search(vector<int>& nums, int target)
{
int low = 0, high = (int)nums.size() - 1;
while (low <= high)
{
int mid = low + (high - low)/2;
if (nums[mid] == target) // Element found
return mid;
else if (nums[mid] < target) // Go right
low = mid + 1;
else if (nums[mid] > target) // Go left
high = mid - 1;
}
return -1; // Element doesn't exist in the array
}
Problem 1: https://leetcode.com/problems/binary-search/
You can try solving the problem in the language of your choice. Pretty straight forward.
Now, let's try another problem. Let's say we need to find the index of first occurence of an element in the array.
nums = [2, 3, 4, 4, 4, 4, 9]
target = 4
We, need to find the index of first occurence of 4. In the first iteration we have mid as 3. But, can we return it? Ofcourse, we cannot because the first occurence of 4 is at index 2.
So, what's the solution? How to go about it? How to decide if we want to stop or look for better answers?
Keep track of the answer in a variable ans. If you encounter that nums[mid] is equal to target, then store that mid in ans as a potential answer but also go left to explore more possibilities. If better answer exists, update the ans variable. After while loop is over, return ans.
The code hence is now modified as follows:
int firstOccurence(vector<int>& nums, int target)
{
int low = 0, high = (int)nums.size() - 1;
int ans = -1;
while (low <= high)
{
int mid = low + (high - low)/2;
if (nums[mid] == target)
{
ans = mid;
high = mid - 1; // Look for better answer to the left
}
else if (nums[mid] < target)
{
low = mid + 1;
}
else if (nums[mid] > target)
{
high = mid - 1;
}
}
return ans;
}Now, another problem. Let's say we wanted the rightmost occurence of the target number.
The idea is same. If nums[mid] is same as target, save it as a potential answer but this time we go right because we need the rightmost occurence.
So, the code is:
int lastOccurence(vector<int>& nums, int target)
{
int ans = -1;
int low = 0, high = (int)nums.size() - 1;
while (low <= high)
{
int mid = low + (high - low)/2;
if (nums[mid] == target)
{
ans = mid;
low = mid + 1; // Go right for better answers
}
else if (nums[mid] < target)
{
low = mid + 1;
}
else if (nums[mid] > target)
{
high = mid - 1;
}
}
return ans;
}
Problem 2: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
You can try solving the above problem.
Okay, now we know how solve first and last occurence. Let's take this a step ahead and learn how to think about binary search problems. ( I learnt this from a YouTube channel called "Erricto". I found really good explanations for binary search and dynamic programming on his channel.)
Problem 3:
Given a sorted array, find the number of negative elements in it.
Now, this is far from what we have learnt. We have no particular value to look for. No target. So, how to go about it?
Let's say that the array is
Index 0 1 2 3 4 5 6 7 8 9 10
nums = [-101, -99, -54, -21, -3, 6, 12, 19, 20, 74, 92]Now, below each element, I shall write True(T) or False(F) depending on the following condition:
If nums[index] < 0, I will mark as true (T) else I mark as false (F)
So, how does it look now?
Index-> 0 1 2 3 4 5 6 7 8 9 10
nums = [-101, -99, -54, -21, -3, 6, 12, 19, 20, 74, 92]
Bool -> T T T T T F F F F F FNow, if somehow we were able to find first index which we marked as false (F), would we able to get our answer?
Turns out that yes, we can. Since, false indicates that it is not negative and first false means that all elements to the left are negative. So, how many of them? The index itself. Didn't get it? What is the index of first F for above nums? It's 5 right. So the answer is 5. You can verify it.
What's important is that we think of binary search array as some array with
- Prefixes of True(T) and Suffixes of False(F) OR
- Prefixes of False (F) and Suffixes of True(T) OR
- All True(T)
- All False(F)
And how to derive these true or false values. It's through the conditions given in the question and it's easy to think about. You will realize that there are various ways to frame the conditions for true/false and all are correct.
Let's try some more problems.
Problem 4: https://leetcode.com/problems/koko-eating-bananas/
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko 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 will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Intuition:
We need to find minimum k. So, first let's decide on the range of k. What will be low and high?
Low will be 1 because she needs to eat atleast 1 banana in one hour. What will be high? It will be the maximum value in the array because you only eat from one pile in an hour. So, max speed in one hour will be max bananas in a pile.
Now, think of values of k.
k = [1, 2, 3, 4, 5, 6, ....... high]
Now, how to frame the values of True and False? Simple. If Koko can eat all bananas with k speed within h hours, we will mark as true. Now, just tell me one thing. If you can eat a pizza with some speed s within time T then with speed (s+1), would you still be able to eat within time T? The answer is yes because we are eating faster.
So, if for some k, the condition is true, for every k after it, the condition will be true, right?
So, what's the problem changed to?
Finding the first k for which the condition evaluates to true.
Finding the first k for which we can eat all bananas within 'h' hours.
I hope you got it.
The implementation is as follows:
class Solution {
private:
int hoursRequired(int speed)
{
int cnt = 0;
for(int c: arr)
{
cnt += c/speed + (c % speed != 0);
}
return cnt;
}
public:
int minEatingSpeed(vector<int>& piles, int H) {
const int n = (int)piles.size();
int maxElement = 0;
for (int i = 0; i < n; ++i)
{
maxElement = max(maxElement, piles[i]);
}
int ans = -1, low = 1;
int high = maxElement; // Max element in the array
while(low <= high)
{
int mid = low + (high - low)/2;
int timeRequired = hoursRequired(mid); // Hours required to eat all bananas with speed as 'mid'
if(timeRequired <= H) // Condition has evaluated to true
{
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
return ans;
}
};Now, let's talk about the time complexity of a problem which can be solved using binary search.
The complexity depends on two things.
-
Search space: Since, the space is divided by 2 everytime,
n -> n/2 -> n/4 -> n/8 ...... -> 1, the number of steps is log2(n) or more specifically log2(search space)
PS : Please note that this is the log of the search space which may or may not be equal to the number of elements in the given input array! -
For each step, we do some calculations, to find if the condition is true or false. So, if O(x) is the time required for finding if the condition evaluates to true or false, then the total time complexity of the solution will be O(x * log2(range));
For the example of Koko eating bananas, the time complexity will be O(n * log2(maxElement));
That's it. You can actually solve other binary search problems using the tag search option provided by Leetcode.
Happy Leetcoding and binary searching!