5 notes tagged
Lower bound vs upper bound binary search explained: first index >= target vs first index > target, with ready templates in Python, Java and C++.
Find Right Interval (LeetCode 436): sort interval starts and binary-search the smallest start >= each interval end, O(n log n).
Find K Closest Elements (LeetCode 658): binary search the best window start so the k-length window is closest to x, in O(log(n-k)+k).
Find First and Last Position of a target in a sorted array (LeetCode 34) using two binary searches (lower and upper bound) in O(log n).
Search Insert Position (LeetCode 35): use lower-bound binary search to find where a target is or should be inserted, in O(log n).