二分查找：是否存在low != high循环条件导致错误的场景？

Question

这里有两种二分查找的实现，唯一的区别是 for 循环条件。

注意：如果你不知道 go，则没有 while 循环，但在这种情况下，你可以在你的脑海中用“for”代替“while”，如果这样更容易的话——它的功能是相同的。

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 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
}

我注意到正在更改< for a != works in 所有测试用例，但是如果您查找理想的二分搜索，他们会使用<, 这是为什么？如果使用 !=，什么数组 + 目标会导致问题（如果有）？

据我所知，高不可能小于低，只能大于或等于。一旦它们相等，循环就会退出，因为算法找到了目标所在位置或目标所在位置的索引。

PS：我知道如果找不到索引，这些不会返回-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)
    }
}

谢谢！

Answer 1

在这个实现中，它没有任何真正的区别，因为我们总是有

low <= high

，所以

low != high

和

low < high

总是等价的。

我总是写这个

low < high

，但是，因为我发现它可以更容易地向自己证明我的二分搜索有效，这是你应该总是做的事情，而且我认为，如果我在实现中犯了错误,

low < high

将使该错误的影响不太可能是灾难性的。