小编典典

进行递归二进制搜索

go

我知道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。为什么?


阅读 73

收藏
2020-07-02

共1个答案

小编典典

二进制搜索的逻辑是合理的。唯一的问题是您忘记了将每个递归调用的结果分配给indexfound

当前,您有以下这些递归调用:

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)
2020-07-02