进行递归二分搜索 [英] Go recursive binary search

问题描述

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

这是我的代码：

pre $ $ $ $ $



func BinarySearch（data [] int， target int，low int，high int）（index int，found bool）{
mid：=（high + low）/ 2
if low>高{
索引= -1
找到=假
} 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 。为什么？

解决方案

您的二进制搜索的逻辑是合理的。唯一的问题是你忘记了将每次递归调用的结果分配给 index 和找到。现在你有这些递归调用：

  BinarySearch（data，target，低，中 -  1）
 // ... 
 BinarySearch（数据，目标，中+ 1，高）
  

您只需分配结果：

  index，found = BinarySearch（data，目标，低，中 -  1）
 // ... 
索引，找到= BinarySearch（数据，目标，中+ 1，高）
  pre> 
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?
解决方案
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)


                        
这篇关于进行递归二分搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！