Let us go through some of the common problems related to binary search technique.
Problem: https://leetcode.com/problems/search-insert-position/
In this case, the question asks to return the index at which the target should be added, if it is missing. If not missing, then we return the index of its location.
We begin with the code and as we can tell, it is a regular binary search code.
public int searchInsert(int[] A, int target) {
int low = 0, high = A.length-1;
while(low<=high){
int mid = (low+high)/2;
if(A[mid] == target) return mid;
else if(A[mid] > target) high = mid-1;
else low = mid+1;
}
return low;
}
If an element is not found, then the position at which it needs to be inserted is lo. This is because, we break out of loop when (lo <= hi) breaks then that means that both lo and hi did not produce the search and so, when lo cross-over beyond hi, then that is the position at which we need to insert. Let us see some examples:
This is a pattern that can be used for several problems.
In these problems use an anchor point (say the last element of the array -- it can also be the first element but let us stick with the last element).
There are two hemispheres (parts) here and in each hemisphere, we can go either left or right.
Another approach is search the minimum. And then search in the left part and search in the right part.
Problem: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
Here are the steps:
Duplicates in an array can make things difficult since the a[mid] can become same as a[anchor] and in that case, we do not know, which way to go. In other words, if we have a case like like [2,<<2>>,2, 2, 5,6,0,0,1, <<2>>, 2, 2] and if you get stuck in the plateau of 2 (on the left or right) which is also the anchor, then we don't know whether we need to go left or right.
The solution here is to squeeze the range one by one. Handling Duplicates can be handling essentially by squeezing the range.
Problem: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
As compared to "Find Minimum in Rotated Sorted Array", this variant has duplicates in it and so cannot be done in log(N). So, we squeeze the range till we have (a[left] != a[mid]) or (a[right] != a[mid])
Consider the example (3,3, 3, 3,1,3), here if the mid falls to one of the 3 on the left, then we would not know, which way to go.
So, we can use the range-search. Based on the range-search, we also do hi--, if the elements are same. If we do lo++, it does not work (since we are comparing a[mid] with a[hi]). Like the other ones, we also return a[lo]
Use similar approach to the case, when we have to find minimum in rotated sorted array with no duplicates. To do that, we compare num[mid] with num[hi] (just like range-search)
When num[mid] == num[hi], we can't be sure the position of minimum in mid's left or right, so just let upper bound reduce one. Why can't we reduce the lower? This is because, we are comparing nums[mid] with nums[hi]. If they are same, then we should reduce hi--. Increasing lo++ would not help.
public int findMin(int[] nums) {
int lo = 0, hi = nums.length-1, mid = 0;
while(lo < hi) {
mid = lo + (hi - lo)/2;
if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else if (nums[mid] < nums[hi]) {
hi = mid;
} else { // when num[mid] and num[hi] are same
hi--;
}
}
return nums[lo];
}
Problem: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
Once again, the array has duplicates.
bool search (int* nums, int numsSize, int target) {
int i, l = 0, h = numsSize -1, m;
while (l <= h) {
m = l + (h-l)/2;
if (target == nums[m]) return true;
// the only difference from the first one is that we need to squeeze the range
// tricky case, just update left and right
if (nums[m] == nums[l]) {
l++;
} else if (nums[m] == nums[h]) {
h--;
} else if (nums[m] < nums[numsSize-1]) {
// If you are in second hemisphere
if ((target > nums[m]) && (target <= nums[numsSize-1])) {
l = m + 1;
} else {
h = m -1;
}
} else {
// If you are in first hemisphere
if ((target < nums[m]) && (target > nums[numsSize-1])) {
h = m -1;
} else {
l = m + 1;
}
}
}
return false;
}
Problem: https://leetcode.com/problems/find-peak-element/
In this case, all elements are different and so we do not have an issue here. But, if elements can be duplicates, then we need to handle duplicates here as well.
This is fairly straightforward application of binary search. Compare the mid-point with left and with right. If you are less than left, go left. If you are less than right, go right. Why does this work?
Very important: a[-1] and a[len] are equal to INT_MIN and not INT_MAX!
Here is the code.
int findPeakElement(int* a, int len) {
int lo = 0, hi = len -1, mid, left, right;
if (!len) return -1;
while (lo <= hi) {
mid = lo + (hi-lo)/2;
// Keeping variables left/right makes the code less messy
left = (mid == 0) ? INT_MIN : a[mid-1];
right = (mid == (len-1)) ? INT_MIN : a[mid+1];
if (a[mid] < right) {
lo = mid + 1;
} else if (a[mid] < left) {
hi = mid -1;
} else {
return mid;
}
}
return -1;
}
Problem: https://leetcode.com/problems/longest-repeating-substring/
When searching in strings, sometimes we can also do binary-search over length of the substring. Binary search over the length of the substring -- if possible, seek higher value, else seek lower value.
We can use a rolling hash since each substring itself will cost O(N). With rolling hash, we can eliminate that to O(1) for each substring. So, if we can start the substrings (of the order of N), then for each substring, we would end up walking L. Thus, we will have a total of O(N*L) operations for each trial. Now, there are logL such operations. So, the total complexity would be O(N*L*logL). With rolling hash, this will become O(N*logL)
class Solution {
const int Mod = int(1e9) + 123; // prime mod of polynomial hashing
const int Base = 26;
int c2i(char ch) {
return ch - 'a';
}
bool search(const string& S, int L) {
unordered_set<long long> hashes;
long long hash = 0;
long long pow = 1;
// build the initial rolling hash
for (int i = 0; i < L; ++i) {
hash = (hash * Base + c2i(S[i])) % Mod;
pow = (pow * Base) % Mod;
}
hashes.insert(hash);
// update the rolling hash
for (int i = L; i < S.length(); ++i) {
// remove last character
hash = (hash * Base - c2i(S[i - L]) * pow + Mod) % Mod;
// add new character
hash = (hash + c2i(S[i])) % Mod;
if (!hashes.insert(hash).second) {
// todo: check for collisions
return true;
}
}
return false;
}
public:
int longestRepeatingSubstring(string S) {
const int N = S.length();
int l = 1;
int r = N - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (search(S, mid)) {
l = mid;
}
else {
r = mid - 1;
}
}
return search(S, l) ? l : l - 1;
}
};
Problem: https://leetcode.com/problems/arranging-coins/
You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete. Given the integer n, return the number of complete rows of the staircase you will build.
Basically, do a binary search of the space (1)*(1+1)/2 and (n)*(n+1)/2. In the end, lo would exceed hi by 1. So, we can return hi (or lo-1). We can also keep adding the next step (1, 2, 3, 4, 5, 6.. but this would lead to TLE (Time Limit Exceeded) error).
This is pretty cool since the binary search is being done on the Summation itself.. n(n+1)/2
public int arrangeCoins(int n) {
if (n == 0) return 0;
long N = (long)n;
long lo = 1, hi = N;
while (lo <= hi) {
long mid = lo + (hi-lo)/2;
long temp = mid * (mid +1)/2;
if (temp > N) hi = mid-1;
else if (temp < N) lo = mid+1;
else return (int)mid;
}
return (int)(hi);
}
A lot of problems are modeled after binary range search. These problems usually have a continuity in terms of the range of solutions and the goal may be to pick one of them solutions (max or min). Some of the problems are as follows:
Problem: https://leetcode.com/problems/koko-eating-bananas/
Continuity: if Koko can eat at rate 4 to get to H, then she can also eat at 5, 6, and so on to get to H. We want to pick the min of these possible values. In this example, the range is [4, INFINITY]
Pick up 0 as lo, Integer.MAX_VALUE as hi and then check if mid is something that is possible. Like other ranges, here are few things to keep in mind:
Btw, if we were to take sum as the initial high-value, then it is possible that with high values, the sum might overflow. So, it is better to simply take the high value as Integer.MAX_VALUE.
For canEat() method, we should go over each element and take the Math.ceil((double)element/mid) -- this would give the number of hours it would take to finish those many bananas. We should keep a running counter. If at some point, the counter exceeds H, then we should return false since it is not possible. If not, then in the end, we should return true.
public int minEatingSpeed(int[] piles, int H) {
int lo = 0, hi = Integer.MAX_VALUE, mid = 0, ret = hi;
while (lo < hi) {
mid = lo + (hi-lo)/2;
if (canEat(piles, mid, H)) {
ret = mid;
hi = mid;
} else {
lo = mid +1;
}
}
return ret;
}
private boolean canEat(int[] piles, int mid, int H) {
int count = 0;
for (int elem: piles) {
count += (int)Math.ceil((double)elem/mid);
if (count > H) return false;
}
return true;
}
Problem: https://leetcode.com/problems/divide-chocolate/
Continuity: if minimum sweetness of 10 is okay, then we can go minimum to smaller values as well (we should be able to split the smallest array into lesser elements). So, we want to pick the maximum of these possible values. In this example, the range is [1, 3, 5] and want to return 5.
Need to take into account when K = 0. In that case, the whole thing belongs to the user and so, we can simply return the sum.
public int maximizeSweetness(int[] sweetness, int K) {
int ret = 0, lo = 0, sum = 0, hi = Integer.MAX_VALUE;
for (int elem: sweetness) sum += elem;
if (K == 0) return sum;
while ( lo < hi) {
int mid = lo + (hi-lo)/2;
if (possible(sweetness, K, mid)) {
ret = mid;
lo = mid + 1;
} else {
hi = mid;
}
}
return ret;
}
boolean possible(int[] sweetness, int K, int mid) {
int count = 0, sum = 0;
for (int elem: sweetness) {
if ((sum + elem) >= mid) {
count++;
sum = 0;
} else sum += elem;
}
return (count >= (K+1)) ? true : false;
}
Problem: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
Continuity: If we can use ship weight of 15 to ship within D days, then we can also use the ship weight of 16, 17, and so on. Our goal is to find the minimum value in that (sorted) range. In this example, the range is [15, INFINITY]
This is similar to the "Koko Eating Bananas" problem. Also, it is a good idea to cache the res in the main binary loop, whenever the value is possible. Finally, return the res.
Here is the code:
public int shipWithinDays(int[] weight, int D) {
int lo = 0, hi = Integer.MAX_VALUE, mid = 0, res = 0;
while (lo < hi) {
mid = lo + (hi-lo)/2;
if (canShip(weight, mid, D)) {
hi = mid;
res = mid;
} else {
lo = mid+1;
}
}
return res;
}
private boolean canShip(int[] weight, int mid, int D) {
int count = 1, sum = 0;
for (int elem: weight) {
if (elem > mid) return false;
sum += elem;
if (sum > mid) {
// If sum is higher than we need to start fresh with the current element as sum.
sum = elem;
count++;
if (count > D) return false;
}
}
return true;
}
Problem: https://leetcode.com/problems/minimize-max-distance-to-gas-station/
Continuity: Let the answer be X and the maximum Gap be G, then it is possible to put all K within two gas-stations (other than the two with the gap G) and thus have the max Gap of G. In this example, the range is [X, GAP] and we are looking for the minimum value of that range.
In this problem, the item that needs to be explored is the distance between the two gas stations when we add a new gas station.
So, the range can be [0, last_value-first_value]. For every midpoint, we call a function (say possible()) to check if it is possible that we can have k gas-stations with the given value of distance (identified by mid).
If possible() returns true, then that means the current value is lower and we need to go higher (by setting left = mid). If possible() returns false, then that means the current value is higher and we need to go lower (by setting right=mid).
Since the values are decimals, we CANNOT use left=mid+1 or right=mid-1. Instead, all we can do is to use left=mid and right=mid.
The possible() function checks if it is possible to put k gas-stations with the value of the passed mid. To do that, we consider the distance between two consecutive (existing) gas-stations (a[i] and a[i+1]). We divide that by the mid, and subtract 1 (we subtract 1 to account for the edge). Next, we add this to a count. If the count becomes >= k, then we return true.
Here is the code in C:
double minmaxGasDist(int* a, int len, int k) {
double l = 0, r = INT_MAX, mid;
while ((r - l) > 0.0000001) {
mid = (r+l)/2;
if (possible(a, len, k, mid)) l = mid;
else r = mid;
}
return r;
}
bool possible (int* a, int len, int k, double mid) {
int i, count = 0;
for (i = 1; i < len; i++) {
count += ceil((a[i]-a[i-1])/mid)-1;
if (count > k) return true;
}
return false;
}
Problem: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
Continuity: Let the Kth number be X and K+1th number be Y, then all the numbers in the range [X, Y] are answers.
For this case, the range of search is the first element (a[0][0]) and the last element (a[n-1][n-1]).
When we get a mid, we do another binary-search for all rows and count the number of elements that are bigger than mid. Note that it is possible that the mid value may not even exist in the array. Since we are incrementing lo by 1, even if mid does not exist, then mid would be increased to a value that is equal to what is there in the table..
If the number of elements are smaller than the mid, then we make the lo become mid+1.
Else, we set hi to mid -- this is because, we would like the lo to catch up. May be, mid does not exist. Or, may be there are duplicate elements.
int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
int n = matrixRowSize, t_lo = 0, t_hi, t_mid, mid, count ;
int *row;
int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
mid = lo + (hi-lo)/2;
count = 0; // number of elements not bigger than mid
// Visits all the rows. For each row, count the number of elements smaller than
// the selected value.
for (int i = 0; i < n; i++) {
count += get_count_smaller_elements_than_k(matrix[i], n, mid);
}
// if count >= k, then let the lo catch up to hi. Since the elements may
// have duplicates plus mid may not exist in the array.
if (count < k) lo = mid + 1;
else hi = mid;
}
return lo;
}
int get_count_smaller_elements_than_k (int *a, int n, int k) {
int t_lo = 0, t_hi = n-1, t_mid;
while (t_lo <= t_hi) {
t_mid = t_lo + (t_hi-t_lo)/2;
if(a[t_mid] > k) {
t_hi = t_mid - 1;
} else {
t_lo = t_mid + 1;
}
}
return t_lo;
}
https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/
Continuity: Similar to the "Kth Smallest Element in a Sorted Matrix" problem.
We use range search and instead of the usual possible() function, we use a function for counting the number of elements in a row. Here we process each row (in the multiplication table) however, for finding the count, we can just take minimum of (v/i and n). Let us understand v/i thing. Let us say,w e have the m=2 and n=6, so the table becomes
1 2 3 4 5 6 2 4 6 8 10 12
Now, if we want to find the number of elements smaller than 5, then for the first row, it would be min(5/1, 5 ) or 5. For the second row, it would be min(5/2, 5) or min(2, 5) so the answer would be 2!
Btw, why would the selected number (mid) exist in the table? Well, let us say, the Kth number is X and the K+1th number is Y. Then the binary range would search the value X going from a large range till it hits X. If it reaches Y, then the lo and hi have still not met and it will continue to search till it reaches X..
Here is the code:
int findKthNumber(int m, int n, int k) {
int low = 1 , high = m * n + 1, res = 0;
while (low < high) {
int mid = low + (high - low) / 2;
int c = count(mid, m, n);
if (c < k) {
low = mid + 1;
} else {
high = mid;
res = mid;
}
}
return res;
}
int count(int val, int m, int n) {
int count = 0;
for (int i = 1; i <= m; i++) {
int temp = min(val/i , n);
count += temp;
}
return count;
}
Problem: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
The idea here is that give a number n, we know the number of trailing zeros.
In this question, we are asking what number would have these many trailing zeros. To do that, we can do binary search. We start with lo=0 and hi=10^9. For every mid, we find out the number of trailing zeros.
The zero number would happen because sometimes at numbers that have more than one 5 divisors, then number of K can jump. As shown below, the number of trailing zeros jumps to 6 when go to 25. So, there is no number for which the trailing zeros are 5.
0 -- 0 5 -- 1 10 -- 2 15 -- 3 20 -- 4 25 -- 6
So, the steps are:
Here is the code:
int preimageSizeFZF(int K) {
long lo = 0, hi = 1000000000, mid;
int temp;
if (!K) return 5;
while (lo <= hi) {
mid = lo + (hi-lo)/2;
temp = trailingZeroes(mid);
if (temp < K) {
lo = mid + 1;
} else if (temp > K) {
hi = mid -1;
} else {
return 5;
}
}
return 0;
}
int trailingZeroes(int n) {
int cnt = 0, den = 5;
while(n >= den){
cnt += n/den;
den *= 5;
}
return cnt;
}
Problem: https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/
Continuity: If it takes X days to make m boquets, then the same can be done in X+1 days as well. So, the range is [X, INFINITY]
Note that adjacent do not mean adjacent in the array.. They mean adjacent flowers that have bloomed..
Here is the code:
int minDays(vector<int>& bDay, int m, int k) {
if (m * k > bDay.size())
return -1;
auto lo = 1, hi = 1000000000;
while (lo < hi) {
auto mid = (hi + lo) / 2;
if (canHarvest(bDay, mid, m, k))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
bool canHarvest(vector<int>& bDay, int harvestDay, int m, int k) {
int adjacent = 0;
for (auto bloomDay : bDay) {
adjacent = bloomDay <= harvestDay ? adjacent + 1 : 0;
if (adjacent == k) {
adjacent = 0;
--m;
}
}
return m <= 0;
}