Go recursive binary search

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?

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)

Logic for Binary Search

• Target is to search for an item in an array.
• Get the middle item of the array.
• If more than the desired value => First item till the end item.
• If less than the desired value => Middle item till the end item
• Repeat process

We implement this using recursion or a loop.

Using recursion to make a binary search

Function will include an array where we will do a search. Then target value is equal to the value we are searching for.<br>
lowIndex will indicate the begining of our search.<br>
highIndex indicates the last position of our search.<br>
Then the function returns the position of the target value we are searching for.<br>
The reason for including the lowIndex and highIndex in the arguments is to search a subset of the array.

func binarySearch(array []int, target int, lowIndex int, highIndex int) int {
	//specify condition to end the recursion
	if highIndex < lowIndex {
		return -1
	}
	// Define our middle index 
	mid := int((lowIndex + highIndex) / 2)
	if array[mid] > target {
		return binarySearch(array, target, lowIndex,mid)
	}else if array[mid] < target {
		return binarySearch(array, target,mid+1,highIndex)
	}else {
		return mid 
	}
}

Using a loop to make a binary search

func iterbinarySearch(array []int, target int, lowIndex int, highIndex int) int {
	startIndex := lowIndex
	endIndex := highIndex

	var mid int

	for startIndex < endIndex {
		mid = int((lowIndex + highIndex) / 2)
		if array[mid] > target {
			return binarySearch(array, target, lowIndex, mid)
		} else if array[mid] < target {
			return binarySearch(array, target, mid+1, highIndex)
		} else {
			return mid
		}

	}
	return -1
}

http://play.golang.org/p/BbL-y7pJMi

Works fine as far as I can tell.