## CodingBison

Let us go through some of the common problems related to binary search technique.

#### 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:

• Example 1 : [4, 5, 6] target = 9 (as in cases of stack, it is a good idea to start with extreme examples like (1, 2, 3, 4) or (, 4, 3, 2, 1)).
• In this case, we will start with lo = 0 and hi=2. Now, mid = 1 and target is higher and so we would go right.
• We now have lo = 2, hi = 2 and so mid = 2. Since 9 is higher than a[mid], we will increase lo.
• So, in this case, lo will keep increasing and hi will remain fixed. This will happen till lo surpasses hi.
• Example 2 : [4, 5, 6] target = 3
• In this case, we will start with lo = 0 and hi=2. Now, mid = 1 and target is lower and so we would go left.
• We now have lo = 0, hi = 0 and so mid = 0. Since 3 is lower than a[mid], we will decrease hi.
• So, in this case, hi will keep decreasing and lo will remain fixed. This will happen till hi surpasses lo and goes on the left.
• Example 3 : [1, 2, 4, 8, 20] and target = 9
• We start with lo/hi as 0/3.. mid is 2 and a[mid] < 9 and so we move right and increase lo. So, we have lo/hi as 3/3.
• With lo/hi as 3/3.. mid is 3 and a[mid] < 9 and so we move right and increase lo. So, we have lo/hi as 4/3.
• lo is higher now and we need to insert at 4.
• Example 4 : [1, 2, 4, 8, 20] and target = 3
• We start with lo/hi as 0/3.. mid is 2 and a[mid] > 3 and so we move left and decrease hi. So, we have lo/hi as 0/1.
• With lo/hi as 0/1.. mid is 0 and a[mid] < 3 and so we move right and increase lo. So, we have lo/hi as 1/1
• With lo/hi as 1/1.. mid is 1 and a[mid] < 3 and so we move right and increase lo. So, we have lo/hi as 2/1
• lo is higher now and we need to insert at 2.
• We likely need to insert this at lo since the division of (lo +hi)/2 yields an integer and that is the floor.

#### Search in Rotated Sorted Array

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.

• If we are in the second hemisphere,
• then we need to go right, if the value being searched is greater than a[mid] but lower than a[anchor]
• then we need to go left, if the value being searched is less than a[mid] but lower than a[anchor]
• then we need to go left, if the value being searched is higher than a[mid] and also higher than a[anchor]
• So, we need to go left for two reasons and right for one reason. It is simpler to code to go to the right and for the remaining cases, go left.
• If we are in the first hemisphere,
• then we need to go right, if the value being searched is higher than a[mid] and also higher than a[anchor]
• then we need to go right, if the value being searched is less than a[mid] and also lower than a[anchor]
• then we need to go left, if the value being searched is smaller than a[mid] but higher than a[anchor]
• So, we need to go right for two reasons and left for one reason. It is simpler to code to go to the left and for the remaining cases, go right.

Another approach is search the minimum. And then search in the left part and search in the right part.

##### Find Minimum in Rotated Sorted Array

Here are the steps:

• Simply find the min. Then look for the element in the first half or the second half.
• We can use similar logic to find the minimum as the anchor point but simpler.
• If you are in the second hemisphere, go left
• If you are in the first hemisphere, go right

#### Handling Duplicates in Binary Search

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.

• If we find that a[mid] is same as a[left], then we should increase left. We keep doing this till a[mid] != a[left] and in that case, we might end up with a[mid] being NOT different from a[anchor]
• If we find that a[mid] is same as a[right], then we should decrease the right. We keep doing this till a[mid] != a[right] and in that case, we might end up with a[mid] being NOT different from a[anchor]

##### 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];
}
```

##### 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;
}
```

#### 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;
}
```

#### 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;
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;
}
};
```

#### 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:

##### 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:

• If mid is possible, then we can try with lesser speed since may be that is possible. For more, we
• use hi =mid and NOT hi = mid + 1 (typical of binary range search)
• If mid is not possible, then we should try for more speed since that might be possible
• Check should be (lo < hi) and NOT (lo <= hi)
• We should return hi or lo and NOT mid

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;
}
```

##### 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.

• Basically, go for the mid (of lo and high); hi can be set to INF. For mid, we need to see, if that is possible.
• go over elements of the array and keep the sum. If the sum becomes >= mid, then increment a count and reset the sum as 0.
• if the count is > (K+1), then it is possible. Why is that? Well, if it is possible to have count >= K + 1, then that means that there are some extra chunks and those can be given to all the friends except for the minimum share.

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;
}
```

##### 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;
}
```

##### 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;
}
```

##### 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) 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, 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;
}
```

##### 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;
}
```

##### 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:

• We are doing a range on the number N and checking for its trailing zeros.
• If a number exists with K+1 0s, then the number that will have K 0s will be to the left.
• If there are numbers with K 0s, then there are always 5 numbers with K 0s. So, the range is only [X,X+1,X+2,X+3,X+4]. We
• just need to confirm that such an X exists we return 5. So, here we are returning the length of the range which is either
• 5 or 0.
• For example, numbers 0!, 1!, 2!, 3!, and 4! all have 0 number of trailing zeros. Next, 5!, 6!, 7!, 8!, and 9! all of these have 1 trailing zeros. So, if the answer is found, then there would be 5 numbers else there would be zero numbers.
• If someone were to ask return the smallest or the largest number, then we can do the same. Or, if we are X+2, then we can go left to get
• the smallest number with K trailing zeros and we can go to the right to get the largest number with K trailing zeros.

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;
}
```

##### 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) {
for (auto bloomDay : bDay) {