Few folks requested offline to share binary search problems for practice and patterns which we generally encounter.
Sharing some good binary search problems (20) for practice.
List: https://leetcode.com/list/xcrx4mxm
Problems where its Difficult to figure out if Binary Search can be applied.
There are patterns of problems where its little difficult to figure out if binary search can be applied.
There would be a given array of length (n) and we need to find minimum which satifies contraint on array.
Runtime of these are normally nLog(m).
https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/
https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/
https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/
https://leetcode.com/problems/koko-eating-bananas/
https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
class Solution {
bool isValid(vector<int>& bloomDay, int m, int k, int mid) {
int count = 0, size = 0;
for (int i = 0; i < bloomDay.size(); i++) {
size = (bloomDay[i] <= mid) ? size+1 : 0;
if (size == k) size = 0, count++;
if (count == m)
return true;
}
return false;
}
public:
int minDays(vector<int>& bloomDay, int m, int k) {
if(bloomDay.size() == 0 || m == 0 || k == 0) return 0;
if (m * k > bloomDay.size()) return -1;
int l = INT_MAX, r = INT_MIN;
for (int i = 0; i < bloomDay.size(); i++) {
l = min(l, bloomDay[i]);
r = max(r, bloomDay[i]);
}
while (l <= r) {
int mid = l + (r-l)/2;
if (isValid(bloomDay, m, k, mid))
r = mid-1;
else
l = mid+1;
}
return l;
}
};Tricky Binary Search
There are multiple conditions we need to figure out if we need to select left or if we need to select right.
https://leetcode.com/problems/find-peak-element/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
https://leetcode.com/problems/search-in-rotated-sorted-array/
https://leetcode.com/problems/missing-element-in-sorted-array/
class Solution {
int findPeakElementUtil(vector<int>& nums, int l, int r) {
if (l > r) return -1;
int m = l + (r-l)/2;
if (((m > 0) && (nums[m] > nums[m-1])) &&
((m < nums.size()-1) && (nums[m] > nums[m+1])))
return m;
if (m == 0 && nums.size() > 1 && nums[m] > nums[m+1])
return m;
if ((m == nums.size()-1) && (nums[m] > nums[m-1]))
return m;
int left = findPeakElementUtil(nums, l, m-1);
int right = findPeakElementUtil(nums, m+1, r);
if (left != -1)
return left;
else
return right;
}
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
if (n == 1) return 0;
return findPeakElementUtil(nums, 0, n-1);
}
};Simple Binary Search
https://leetcode.com/problems/find-smallest-letter-greater-than-target/
https://leetcode.com/problems/missing-element-in-sorted-array/
https://leetcode.com/problems/peak-index-in-a-mountain-array/
https://leetcode.com/problems/h-index-ii/
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
https://leetcode.com/problems/first-bad-version/
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int n = letters.size();
int l = 0, r = n-1;
if (target >= letters[n-1] || target < letters[0])
return letters[0];
int m = 0;
while (l <= r) {
m = l + (r-l)/2;
if (m > 0 && (target >= letters[m-1] && target < letters[m]))
return letters[m];
else if (target >= letters[m])
l = m+1;
else
r = m-1;
}
return letters[m];
}
};Using C++ STL upper bound for binary search
https://leetcode.com/problems/time-based-key-value-store/
https://leetcode.com/problems/online-election/
https://leetcode.com/problems/random-pick-with-weight/
https://leetcode.com/problems/find-right-interval/
For Java script, built in api is not available. Sharing @claytonjwong approach. Thanks to him.
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/692931/Javascript-and-C%2B%2B-solutions
https://gist.github.com/claytonjwong/53bd1c1489b12eccad176addb8afd8e0
class TimeMap {
unordered_map<string, map<int, string>>hm;
public:
/** Initialize your data structure here. */
TimeMap() {
}
void set(string key, string value, int timestamp) {
hm[key].insert({timestamp, value});
}
string get(string key, int timestamp) {
auto it = hm[key].upper_bound(timestamp);
return (it == hm[key].begin()) ? "" : prev(it)->second;
}
};Binary search based on condition on 2 arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
if (n > m)
return findMedianSortedArrays(nums2, nums1);
int k = (n+m-1)/2;
int l = 0;
int r = min(k, n);
while (l < r) {
int mid1 = l + (r-l)/2;
int mid2 = k-mid1;
if (nums1[mid1] > nums2[mid2])
r = mid1;
else
l = mid1+1;
}
/* if (n+m) is odd, the median is the larger one between nums1[l-1] and nums2[k-l] */
int a = max(l >= 1 ? nums1[l-1] : INT_MIN, k >= l ? nums2[k-l] : INT_MIN);
if ((n+m) % 2 != 0)
return a;
/* in case (n+m) is even, take the average of mid 2 elements */
int b = min(l < n ? nums1[l] : INT_MAX, k-l+1 < m ? nums2[k-l+1] : INT_MAX);
return (a+b)/2.0;
}
};Link to similar posts on different topics:
https://leetcode.com/discuss/general-discussion?currentPage=1&orderBy=most_relevant&query=wh0ami