【LeetCode】Binary Search

参考 LeetCode Binary Search Summary 二分搜索法小结 的 python 版
今天偷懒一下，拿以前的小笔记来自我抄袭。

1. 找到确定值的最基础 binary search

def binary_search(nums, target):
    l, r = 0, len(nums)
    while l < r:
        mid = l + (r - l) // 2
        if nums[mid] == target : 
            return mid 
        elif nums[mid] < target:
            l = mid + 1
        else: 
            r = mid
    return -1

可变动的 4 个地方：

1. r 初始化：len(nums) 或 len(nums) - 1
2. while 条件：l < r 或 l <= r
3. r 更新：r = mid 或 r = mid - 1
4. return 值: l 或 r 或 r-1
   不可任意组合，如果是写变形 bsearch 时又可能不照下面的规则，要自行想清楚...

不碰 r 边界的基础 bsearch

r = len(nums)
l < r
r = mid

碰 r 边界的基础 bsearch

r = len(nums) - 1
l <= r
r = mid - 1

2. lower bound

• 查询 target 不一定在 list 中
• 与 target 相同的数有好几个
• 无需 nums[mid] == target 判断

2-1 lower bound: find first x >= target

第一个不小於目标的数

# [1, 1, 2, 3, 6] t = 4 
def bs_lowerbound(nums, target):
    l, r = 0, len(nums)
    while l < r: 
        mid = l + (r - l) // 2
        if nums[mid] < target:
            l = mid + 1
        else: 
            r = mid
    return r

2-2 lower bound 小变化: find last x < target

往前退，就是 最後一个小於目标的数
return r - 1 即可

3. upper bound

• 查询 target 不一定在 list 中
• 与 target 相同的数有好几个

3-1 upper bound: find first x > target

除了 == 部分，其他都一样。

# [1, 1, 2, 3, 6] t = 4 
def bs_upperbound(nums, target):
	l, r = 0, len(nums) 
	while l < r: 
		mid = l + (r - l) // 2 
		if nums[mid] <= target: # == 时也要移动左边界
			l = mid + 1 
		else: 
			r = mid
	return r

3-2 小变化: find last x <= target

return r - 1 即可

4. 用子函数当二分判断的关系（通常由 mid 求出）

难ＱＱ 要经验
Minimize Max Distance to Gas Station
Swim in Rising Water

Split Array Largest Sum
Guess Number Higher or Lower
Find K Closest Elements
Find K-th Smallest Pair Distance
Kth Smallest Number in Multiplication Table
Maximum Average Subarray II
Koko Eating Bananas
Nth Magical Number

5. 其他（target 不固定）

Find Peak Element
H-Index II