CODEWITHSUNDEEP
algorithmgobinary-search
zolamk
zolamk

Reputation: 6387

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?

Upvotes: 0

Views: 2577

Answers (3)

Philip Mutua
Philip Mutua

Reputation: 6891

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.
lowIndex will indicate the begining of our search.
highIndex indicates the last position of our search.
Then the function returns the position of the target value we are searching for.
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
}

Upvotes: 1

Michael Laszlo
Michael Laszlo

Reputation: 12239

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)

Upvotes: 5

mortdeus
mortdeus

Reputation: 197

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

Works fine as far as I can tell.

Upvotes: 0

Related Questions