參考 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