Binary search: is there a scenario where low != high loop condition causes an error?

Question

Here are 2 implementations of Binary search, with the only difference being the for loop condition.

NB: If you don't know go, there are no while loops, but in this case you can substitute "for" for "while" in your mind if it makes it easier - it functions identically.

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
}

What I noticed is changing the < for a != works in all test cases, but if you look up an ideal binary search, they will use <, why is this? And what array + target causes a problem if != is used, if any?

As far as I can understand, it's not possible for high to ever be less than low, only greater than or equal. The loop exits once they're equal as the algorithm has found the index where the target is OR where it SHOULD BE.

PS: I know that these don't return -1 if index not found, it doesn't matter for the question. The full implementation in Go returns (int, bool), bool being false is item not actually found.

Please note my test cases are below:

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

Thanks!

Answer 1

In this implementation, it doesn't make any real difference, because we always have low <= high, so low != high and low < high are always equivalent.

I always write this low < high, however, because I find that it makes it easier to prove to myself that my binary search works, which is something you should always do, and I think that, if I mistake in my implementation, low < high will make the effects of that mistake less likely to be catastrophic.