Go recursive binary search

Question

I know that Go has a sort package that contains search functions, but this is for educational purposes. I've been trying to implement a binary search algorithm in Go but I haven't been able to get it to work.

Here is my code:

package main

import "fmt"

func BinarySearch(data []int, target int, low int, high int) (index int, found bool)  {
    mid := (high + low) / 2
    if low > high {
       index = -1
       found = false
    } else {
        if target < data[mid] {
            BinarySearch(data, target, low, mid - 1)
        } else if target > data[mid] {
            BinarySearch(data, target, mid + 1, high)
        } else if target == data[mid] {
           index = mid
           found = true
        } else {
           index = -1
           found = false
        }
   }
   return
}

func main() {
  data := []int {2, 4, 6, 8, 9, 11, 12, 24, 36, 37, 39, 41, 54, 55, 56,}
  index, found := BinarySearch(data, 8, 0, len(data) - 1)
  fmt.Println(index, found)
}

It always prints 0 false. Why?

Answer 1

The logic of your binary search is sound. The only problem is that you've forgotten to assign the result of each recursive call to index and found.

Currently you have these recursive calls:

BinarySearch(data, target, low, mid - 1)
//...
BinarySearch(data, target, mid + 1, high)

You merely have to assign the results:

index, found = BinarySearch(data, target, low, mid - 1)
//...
index, found = BinarySearch(data, target, mid + 1, high)