二分搜索：使用low != high作为循环条件是否会引发错误？

问题背景 #

我有两个Go语言实现的二分搜索，唯一区别是for循环的条件（可将Go的for视为while），代码如下：

实现1：low < high作为循环条件 #

func BinarySearch(list []int, target int) int {
    low := 0
    high := len(list)

    // Below line is only difference
    for low < high {

        mid := floorAverage(low, high)

        if list[mid] < target {
            low = mid + 1
        } else {
            high = mid
        }
    }

    return low
}

实现2：low != high作为循环条件 #

func BinarySearch(list []int, target int) int {
    low := 0
    high := len(list)

    // Below line is only difference
    for low != high {

        mid := floorAverage(low, high)

        if list[mid] < target {
            low = mid + 1
        } else {
            high = mid
        }
    }

    return low
}

辅助函数 #

func floorAverage(a int, b int) int {
    return (a + b) >> 1
}

我将循环条件从low < high改为low != high后，所有测试用例均能通过，但查阅标准二分搜索实现时，大多使用low < high作为循环条件。请问为何如此？是否存在特定数组与目标值组合，会导致使用low != high时出现问题？

我个人的理解是：high绝不会小于low，只会大于或等于low。当二者相等时循环退出，此时算法已找到目标值的索引，或目标值应插入的位置。另外我知道这些实现未在未找到目标时返回-1，完整的Go实现会返回(int, bool)，bool为false表示未找到目标，这对本次问题无影响。

我的测试用例如下：

func Test_BinarySearch_MultipleTC(t *testing.T) {
    type tc struct {
        list     []int
        target   int
        expected int
    }
    tcs := map[string]tc{
        "Empty list":                                {[]int{}, 0, 0},
        "Single item list target above":             {[]int{5}, 10, 1},
        "Single item list target below":             {[]int{5}, 2, 0},
        "Single item list target match":             {[]int{5}, 5, 0},
        "2 items list target below first":           {[]int{5, 6}, 4, 0},
        "2 items list target match first":           {[]int{5, 6}, 5, 0},
        "2 items list target match end":             {[]int{5, 6}, 6, 1},
        "2 items list target above end":             {[]int{5, 6}, 7, 2},
        "2 items list target between values":        {[]int{5, 7}, 6, 1},
        "Item present in middle of list":            {[]int{1, 2, 3, 4, 5, 6, 7, 8, 9}, 5, 4},
        "Item first item of list":                   {[]int{1, 2, 3, 4, 5, 6, 7, 8, 9}, 1, 0},
        "Item last item of list":                    {[]int{1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 8},
        "Item greater than last item of list":       {[]int{1, 2, 3, 4, 5, 6, 7, 8, 9}, 10, 9},
        "All elements are the same, target matches": {[]int{6, 6, 6, 6, 6, 6, 6}, 6, 0},
        "All elements are the same, target lower":   {[]int{6, 6, 6, 6, 6, 6, 6}, 5, 0},
        "All elements are the same, target higher":  {[]int{6, 6, 6, 6, 6, 6, 6}, 15, 7},
        "Duplicates in list, target matches block":  {[]int{1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5}, 3, 1},
        "Duplicates in list, target between blocka": {[]int{1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5}, 4, 7},
        "Negatives in list":                         {[]int{-5, -3, -1, 1, 3}, -3, 1},
        "Huge list":                                 {BigSlice(0, 9999), 9999, 9999},
    }

    for name, tc := range tcs {
        got := BinarySearch(tc.list, tc.target)

        if got != tc.expected {
            t.Errorf("%v test failed! expected: %v, got: %v", name, tc.expected, got)
        }
        fmt.Printf("%v test passed\n", name)
    }
}

解答 #

在你当前的实现逻辑下，low != high和low < high效果完全等价，不会出现任何问题。但标准实现更倾向于使用low < high，主要有以下几个原因：

1. 语义更直观清晰 #

low < high直接表达了循环的核心逻辑：只要搜索区间[low, high)（左闭右开）内还有至少一个元素，就继续搜索。而low != high只是描述了循环终止的表面条件，没有直观体现区间的有效性，其他开发者阅读代码时需要额外推导逻辑。

2. 容错性更强，避免潜在死循环 #

如果后续修改代码时不小心引入了错误（比如误将high = mid写成high = mid - 1），可能会导致high < low的情况出现。此时low != high会触发无限循环——因为low和high永远不相等，且区间已经无效。而low < high会直接终止循环，避免这种死循环的风险。

3. 符合通用编码习惯 #

绝大多数二分搜索的教程、文档以及标准库实现（比如Go标准库的sort.Search）都采用low < high作为循环条件。遵循通用习惯的代码更容易被其他开发者理解，降低沟通和维护成本。

为什么你的测试用例全部通过？ #

你的实现中，high和low的更新逻辑严格保证了high永远不会小于low：

• 初始状态下high = len(list) >= low = 0
• 每次循环计算的mid = floorAverage(low, high)，必然满足mid >= low且mid < high
  • 执行low = mid + 1时，新的low最多等于high（当high = low + 1时，mid = low，low更新后等于high）
  • 执行high = mid时，新的high必然大于等于low（因为mid >= low）

因此在这个逻辑下，low和high的关系只会是low <= high，low != high完全等价于low < high，自然不会出现问题。

内容的提问来源于stack exchange，提问作者The_Undula