二分法

学习资料：https://www.hello-algo.com/

基础：二分查找元素

def binary_search(nums:[list[int]], target:int)->int:
	# nums已排序
	i, j = 0, len(nums)-1
	while i <= j:
		m = (i+j)//2
		if nums[m] < target:
			i = m+1
		elif nums[m] > target:
			j = m-1
		else:
			return m
	return -1 # 未找到目标元素，返回-1

注意，while后的条件必须包含=，否则考虑两种情况：
1. 若最后一步执行操作为i = m+1，且m+1=j，会导致m+1不会被搜索到。
2. 若最后一步执行操作为j = m-1，且m-1=i，会导致m-1不会被搜索到。

时间复杂度：$O(log\;n)$
空间复杂度：$O(1)$

以上是针对双闭合区间的代码，即以区间 [i, j] 进行查找 target ；左闭右开区间则指以 [i, j) 进行查找。

def binary_search_lcro(nums: list[int], target: int) -> int:
    """二分查找（左闭右开区间）"""
    # 初始化左闭右开区间 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
    i, j = 0, len(nums)
    # 循环，当搜索区间为空时跳出（当 i = j 时为空）
    while i < j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # 此情况说明 target 在区间 [m+1, j) 中
        elif nums[m] > target:
            j = m  # 此情况说明 target 在区间 [i, m) 中
        else:
            return m  # 找到目标元素，返回其索引
    return -1  # 未找到目标元素，返回 -1

---

假设数组存在多个目标值，上述算法将返回其中任意一个索引，这具体取决于算法在搜索过程中选择的中间位置。因此，此时可考虑引入列表进行优化。

def binary_search_list(nums:[list[int]], target:int)->int:
	result = []
	i, j = 0, len(nums)-1
	while i<=j:
		m = (i+j)//2
		if nums[m]<target:
			i = m+1
		elif nums[m]>target:
			j = m-1 # 左闭右开则为 j = m
		else:
			result.append(m)
			# 向左查找 
			left = m - 1 
			while left>=0 and nums[left]==target: 
				indices.append(left) 
				left -= 1 
				# 向右查找 
				right = m + 1 
				while right<len(nums) and nums[right]==target:
					indices.append(right) 
					right += 1 
					break
	return result

---

值得注意的是，由于 $i$ 和 $j$ 都是 int 类型，因此 $i+j$ 可能会超出 int 类型的取值范围；为避免大数越界通常采用公式 $i+\frac{j-i}{2}$来计算中点。

适用场景：

• 有序数据
• 数组
• 数据量较大

扩展 1：二分查找插入点

当数组中无重复元素时，只需将二分查找元素代码最后一行返回值换成 i 即可。
函数将返回最后一个小于目标值的后一个索引（当数组中最小值仍大于目标值时，索引将返回 0 ；当数组中最大值仍小于目标值时，索引将返回 len(list)）。

def binary_search_insertion_simple(nums: list[int], target: int) -> int:
    """二分查找插入点（无重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # target 在区间 [i, m-1] 中
        else:
            return m  # 找到 target ，返回插入点 m
    # 未找到 target ，返回插入点 i
    return i

重点：处理数组中的重复元素

这里当然也可以用列表处理（提取最大索引），但K神给出了更简便的思路。
当查找到目标索引时，我们仍然向更小的方向搜索，算法核心仍然是，我们希望返回最后一个小于目标值的后一个索引。对移动的 j 来说，就是首个小于 target 的元素。

def binary_search_insertion(nums: list[int], target: int) -> int:
    """二分查找插入点（存在重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # target 在区间 [i, m-1] 中
        else:
            j = m - 1  # 首个小于 target 的元素在区间 [i, m-1] 中
    # 返回插入点 i
    return i

我们发现，左闭右开更适合这类“边界”问题。

def binary_search_lcro_insertion(nums:[list[int]], target:int)->int:
	# nums已排序
	i, j = 0, len(nums)-1
	while i < j:
		m = (i+j)//2
		if nums[m] < target:
			i = m+1
		elif nums[m] > target:
			j = m
		else:
			j = m
	return i

扩展 2：二分查找元素边界

查找左边界

等价于上述问题。

查找右边界

法1：寻找 target+1 的左边界索引再 -1

def binary_search_right_edge(nums: list[int], target: int) -> int:
    """二分查找最右一个 target"""
    # 转化为查找最左一个 target + 1
    i = binary_search_insertion(nums, target + 1)
    # j 指向最右一个 target ，i 指向首个大于 target 的元素
    j = i - 1
    # 未找到 target ，返回 -1
    if j == -1 or nums[j] != target:
        return -1
    # 找到 target ，返回索引 j
    return j

法2：构造不存在元素查找

注意，此方法仅适用于 int 类型或选用更小精度的 float。
当数组不包含 target 时，最终 i 和 j 会分别指向首个大于、小于 target 的元素。

def binary_search_new_ele(nums: list[int], target: int) -> tuple[int, int]:
	# 左边界
    i = binary_search_insertion(nums, target - 0.5)
    # 右边界
    j = binary_search_insertion(nums, target + 0.5)-1
    if i == len(arr) or arr[i] != target: 
	    i = -1 
    if j == -1 or arr[j] != target: 
	    j = -1 
    return i, j