递归二分查找

Question

我知道 Go 有一个sort包含搜索功能的包，但这是出于教育目的。我一直在尝试在 Go 中实现二进制搜索算法，但我一直无法让它工作。这是我的代码：package mainimport "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 {

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

}

Answer 3

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

据我所知，工作正常。