二分查找有一些非常值得注意的微妙细节，我们来系统地梳理一下：

1. 循环终止条件

一般使用 while (left <= right) 作为循环条件，这确保了即使在搜索单个元素时也能正确工作。

2. 中间索引计算

使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2 来计算中间索引，这可以防止发生大数相加时的数值溢出（比如发生int32类型的整数溢出）。

3. 更新左右边界

• 如果目标值大于中间值，更新 left = mid + 1
• 如果目标值小于中间值，更新 right = mid - 1

4. 返回值选择

通常返回 left，这是因为:

• 如果找到目标值，left 和 right 最终会收敛到该值。
• 如果未找到目标值，left 将指向大于目标的第一个元素(或数组末尾)。

5. 处理重复元素

如果要找出某个元素第一次出现或最后一次出现的位置，需要稍微调整算法：

• 寻找第一次出现的位置：当 nums[mid] == target 时，更新 right = mid - 1
• 寻找最后一次出现的位置：当 nums[mid] == target 时，更新 left = mid + 1

6. 边界情况

确保考虑了空数组、单元素数组等边界情况。

7. 标准的二分查找实现

from typing import List


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

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

    return -1  # 未找到目标值

8. 实战案例

Q. 输入一个升序排序且满足等差数列规则的整数数组，不幸得是数组里面可能存在某对相邻元素破坏了等差秩序，请找出可能存在的该对相邻元素的索引，不存在直接输出[-1, -1]。例如输入：[0, 1, 2, 3, 4, 6, 7, 8, 9, 10]，输出：[4, 5]。 A. 以下是用 Golang 实现的解决方案

package main

import (
	"fmt"
)

func findBrokenPair(nums []int) []int {
	if len(nums) < 2 {
		return []int{-1, -1}
	}

	l, r := 0, len(nums)-1
	diff := nums[1] - nums[0]
	for l <= r {
		m := l + (r-l)/2
		if (nums[0] + diff*m) == nums[m] {
			l = m + 1
		} else {
			r = m - 1
		}
	}
	
	if l == len(nums) {
		return []int{-1, -1}
	}
	return []int{l - 1, l}
}

func main() {
	fmt.Println((findBrokenPair([]int{1, 3, 5, 7, 9})))                     // [-1, -1]
	fmt.Println((findBrokenPair([]int{0, 1, 2, 3, 4, 6, 7, 8, 9, 10})))     // [4, 5]
	fmt.Println((findBrokenPair([]int{0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11}))) // [4, 5]
	fmt.Println((findBrokenPair([]int{0, 1, 2, 3, 5, 6, 7, 8, 9, 10})))     // [3, 4]
	fmt.Println((findBrokenPair([]int{0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11}))) // [3, 4]
	fmt.Println((findBrokenPair([]int{0, 1, 2, 3, 4, 5, 6, 7, 9, 10})))     // [7, 8]
	fmt.Println((findBrokenPair([]int{0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11}))) // [7, 8]
}

9. 补充：循环不变量原则

二分查找中的循环不变量原则指的是在循环执行的每个步骤中，都保持一个特定条件始终为真，这个条件被称为循环不变量。循环不变量在证明算法正确性方面起着至关重要的作用。

更具体地说，循环不变量应该满足以下几个关键要素：

1. 初始化: 在循环开始之前，循环不变量必须为真。
2. 保持: 在循环的每次迭代中，如果循环不变量在循环开始时为真，那么它在循环结束时也必须为真。
3. 终止: 当循环终止时，循环不变量应该能够帮助我们推导出算法的最终结果是正确的。

例如，在经典的二分查找算法中，循环不变量可以是：

目标值 target 如果存在于数组中，那么它一定存在于当前搜索范围内的数组元素中。

这个循环不变量的解释如下：

1. 初始化: 在循环开始之前，搜索范围是整个数组，因此目标值如果存在，肯定存在于整个数组中。
2. 保持: 在每次循环中，我们根据中间元素的值来缩小搜索范围。如果中间元素等于目标值，则循环结束。否则，我们将搜索范围缩小到中间元素的左侧或右侧，确保目标值仍然存在于新的搜索范围内。
3. 终止: 当循环终止时，要么目标值在中间元素位置被找到，要么搜索范围为空，说明目标值不存在于数组中。

通过维护这个循环不变量，我们就能证明二分查找算法是正确的。