递归二分查找

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

二分查找的逻辑是合理的。唯一的问题是您忘记将每次递归调用的结果分配给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 2

二分查找的逻辑目标是在数组中搜索一个项目。获取数组的中间项。如果超过所需值 => 第一项直到最后一项。如果小于所需值 => 中间项目直到结束项目重复过程我们使用递归或循环来实现这一点。使用递归进行二分查找函数将包含一个数组，我们将在其中进行搜索。那么目标值等于我们要搜索的值。lowIndex将指示我们搜索的开始。highIndex表示我们搜索的最后一个位置。然后函数返回我们正在搜索的目标值的位置。在参数中包含lowIndex和的原因highIndex是搜索数组的子集。func binarySearch(array []int, target int, lowIndex int, highIndex int) int {&nbsp; &nbsp; //specify condition to end the recursion&nbsp; &nbsp; if highIndex < lowIndex {&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; }&nbsp; &nbsp; // Define our middle index&nbsp;&nbsp; &nbsp; mid := int((lowIndex + highIndex) / 2)&nbsp; &nbsp; if array[mid] > target {&nbsp; &nbsp; &nbsp; &nbsp; return binarySearch(array, target, lowIndex,mid)&nbsp; &nbsp; }else if array[mid] < target {&nbsp; &nbsp; &nbsp; &nbsp; return binarySearch(array, target,mid+1,highIndex)&nbsp; &nbsp; }else {&nbsp; &nbsp; &nbsp; &nbsp; return mid&nbsp;&nbsp; &nbsp; }}使用循环进行二分查找func iterbinarySearch(array []int, target int, lowIndex int, highIndex int) int {&nbsp; &nbsp; startIndex := lowIndex&nbsp; &nbsp; endIndex := highIndex&nbsp; &nbsp; var mid int&nbsp; &nbsp; for startIndex < endIndex {&nbsp; &nbsp; &nbsp; &nbsp; mid = int((lowIndex + highIndex) / 2)&nbsp; &nbsp; &nbsp; &nbsp; if array[mid] > target {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return binarySearch(array, target, lowIndex, mid)&nbsp; &nbsp; &nbsp; &nbsp; } else if array[mid] < target {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return binarySearch(array, target, mid+1, highIndex)&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return mid&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1}

Answer 3

http://play.golang.org/p/BbL-y7pJMi据我所知，工作正常。