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 passedn", name)
    }
}

Thanks!