https://leetcode.cn/discuss/post/3579164/ti-dan-er-fen-suan-fa-er-fen-da-an-zui-x-3rqn/

Closed Interval Approach

Find Target

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    # Standard binary search framework, returns index of target element, -1 if not found
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        return -1

Find Left Boundary

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right=mid-1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return left

Left-Closed Right-Open

Find Left Boundary

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def left_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid

    return left

If target doesn’t exist, left-bound binary search returns index of smallest element > target.

<, <=, >, >=

“>=” finds left boundary of target “>” finds left boundary of x+1 “<=” finds (left boundary of x+1) - 1 “<” finds (left boundary of x) - 1

bisect_left finds first index >= target bisect_right returns first position where a[j] > x

Non-Monotonic Arrays

Red (l-1 and left) represents left of target, blue (r and right) represents target and right. nums[n-1] initially blue.

162. Find Peak Element

Compare nums[mid] with nums[mid+1]. Left-closed right-open approach:

1. nums[mid]<nums[mid+1]: peak at mid+1 or right, so l=mid+1
2. nums[mid]>nums[mid+1]: peak at mid or left, r=mid

Note: initialize r=len(nums)-1 to avoid nums[mid+1] overflow. l==r at loop end returns answer. Example: [1,2,3,4].

Left-closed right-open: r and right could be answer, l-1 and left not answer.

1901. Find a Peak Element II

Ling Shen Diagram

Time complexity O(NlogM), binary search on rows. Find max element X in row nums[mid], compare with element A below it. If X < A: from A, monotonic increasing path to peak exists, won’t reach mid row since max of mid row < A. Search below rows for peak.

If X > A: either X is peak or path upward exists to peak.

153. Find Minimum in Rotated Sorted Array

Compare nums[mid] with nums[n-1].

Monotonic Arrays

4. Median of Two Sorted Arrays

Partition arrays, find split line where left elements count = (m+n+1)/2, max left element < min right element. If total odd: answer = max left element If total even: answer = average of max left element and min right element.

Enumerate gaps in first array (m+1 gaps). Binary search for appropriate gap. Make shorter array first to prevent index overflow.

Target split satisfies: nums1[i-1]<nums2[j] and nums1[i]>nums2[j-1], j=(m+n+1)//2-i

Similar: 295. Find Median from Data Stream

Use heaps: left heap and right heap. Left heap can have one more element.

Minimize Maximum

410. Split Array Largest Sum

Traverse array, create new split when current sum > mid, cnt+=1. When cnt==k, return False.

K-th Smallest/Largest

K-th smallest = find smallest x where count of elements ≤ x >= k.

719. Find K-th Smallest Pair Distance

Helper function: count pairs with distance ≤ X. Corresponds to sliding window “shorter is more valid”.

378. Kth Smallest Element in a Sorted Matrix

K-th smallest = smallest x where matrix has at least K elements ≤ x

cntLessEqual(x) returns count of elements ≤ x in matrix. Property: elements ≤ x are in upper left region.

Search from bottom-left: if current element ≤ x, move right, res += i+1 (current row and above all ≤ x).

Why must binary search result be in matrix?

Assume y is smallest element with k elements ≤ y, but y not in matrix. x is first element in matrix > y, then k elements ≤ x (since y not in matrix). Contradiction.

Alternatively: answer must be in [left, right), at loop end interval shrinks to single element = answer.

Others

1539. Kth Missing Positive Number

300. Longest Increasing Subsequence

g[i] represents smallest possible last number for subsequences of length i+1. Traverse array: if new number > last element of g, append to g; else insert at appropriate position in g.