Golang二进制搜索

Question

我正在练习一种采访算法，现在用Go对其进行编码。目的是练习基本的面试算法以及Go的技能。我正在尝试对数字数组进行二进制搜索。

package main

import "fmt"

func main() {
    searchField := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    searchNumber := 23

    fmt.Println("Running Program")
    fmt.Println("Searching list of numbers: ", searchField)
    fmt.Println("Searching for number: ", searchNumber)

    numFound := false
    //searchCount not working. Belongs in second returned field
    result, _ := binarySearch2(searchField, len(searchField), searchNumber, numFound)
    fmt.Println("Found! Your number is found in position: ", result)
    //fmt.Println("Your search required ", searchCount, " cycles with the Binary method.")
}

func binarySearch2(a []int, field int, search int, numFound bool) (result int, searchCount int) {
    //searchCount removed for now.
    searchCount, i := 0, 0
    for !numFound {
        searchCount++
        mid := i + (field-i)/2
        if search == a[mid] {
            numFound = true
            result = mid
            return result, searchCount
        } else if search > a[mid] {
            field++
            //i = mid + 1 causes a stack overflow
            return binarySearch2(a, field, search, numFound)
        }
        field = mid
        return binarySearch2(a, field, search, numFound)
    }
    return result, searchCount
}

我遇到的主要问题是：

1）当列表中的数字高于中间搜索时，我是真的继续二进制搜索，还是转为顺序搜索？我该如何解决？我放置的另一个选项已被注释掉，因为它会导致堆栈溢出。

2）我想添加一个步数以查看完成搜索需要多少步。也可以与其他搜索方法一起使用。如果我按原样打印搜索计数，它将始终读取一个。那是因为我需要在方法中返回它（并因此在标题中调用它）？

我了解Go具有简化此过程的方法。我正在尝试增加我的知识和编码技能。感谢您的投入。

Answer 1

您没有正确执行二进制搜索。首先，您的for循环是无用的，因为条件树中的每个分支都在其中包含一个return语句，因此它永远不能运行多次迭代。看来您开始迭代地进行编码，然后交换为递归设置，但仅对其进行了一半转换。

二进制搜索的想法是，您有一个高低索引，然后搜索它们之间的中点。您并没有这样做，只是增加了field变量并再次尝试（这将使您对每个索引进行两次搜索，直到通过列表末尾找到该项目或段错误为止）。不过，在Go中，您无需跟踪高低索引，因为您可以根据需要简单地对搜索字段进行细分。

这是一个更优雅的递归版本：

func binarySearch(a []int, search int) (result int, searchCount int) {
    mid := len(a) / 2
    switch {
    case len(a) == 0:
        result = -1 // not found
    case a[mid] > search:
        result, searchCount = binarySearch(a[:mid], search)
    case a[mid] < search:
        result, searchCount = binarySearch(a[mid+1:], search)
        result += mid + 1
    default: // a[mid] == search
        result = mid // found
    }
    searchCount++
    return
}

https://play.golang.org/p/4zLgX-_0ZS

Answer 2

func BinarySearch(a []int, x int) int {
    r := -1 // not found
    start := 0
    end := len(a) - 1
    for start <= end {
        mid := (start + end) / 2
        if a[mid] == x {
            r = mid // found
            break
        } else if a[mid] < x {
            start = mid + 1
        } else if a[mid] > x {
            end = mid - 1
        }
    }
    return r
}