进行递归二分查找

Question

我知道 Go 有一个包含搜索功能的 sort 包，但这是出于教育目的。我一直在尝试在 Go 中实现二进制搜索算法，但我一直无法让它工作。

这是我的代码：

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

它总是打印 0 false。为什么？

Answer 1

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

据我所知工作正常。

Answer 2

你的二分查找逻辑很合理。唯一的问题是您忘记将每个递归调用的结果分配给 index 和 found.

目前您有这些递归调用：

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

您只需分配结果：

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

Answer 3

二进制搜索的逻辑

目标是搜索数组中的项目。
获取数组的中间项。
如果超过所需值 => 第一项到最后一项。
如果小于期望值=>中间项到最后一项
重复过程

我们使用递归或循环来实现它。

使用递归进行二分查找

函数将包含一个数组，我们将在其中进行搜索。那么目标值就是我们要搜索的值。
lowIndex 将指示我们搜索的开始。
highIndex 表示我们搜索的最后位置。
然后函数returns我们要搜索的目标值的位置
在参数中包含 lowIndex 和 highIndex 的原因是搜索数组的一个子集。

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

使用循环进行二分查找

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
}

进行递归二分查找

Go recursive binary search

algorithm

binary-search

go

二进制搜索的逻辑

使用递归进行二分查找

使用循环进行二分查找