我正在练习面试算法,现在用 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)我想添加步数来查看完成搜索需要多少步。也可以与其他搜索方法一起使用。如果我按原样打印搜索计数,它总是显示为 1。这是因为我需要在方法中返回它(因此在标头中调用它)吗?
我了解 Go 有简化此过程的方法。我正在努力增加我的知识和编码技能。感谢您的意见。
您没有正确进行二分搜索。首先,您的
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)
if result >= 0 { // if anything but the -1 "not found" result
result += mid + 1
}
default: // a[mid] == search
result = mid // found
}
searchCount++
return
}
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
}
偏离主题,但可能会帮助其他人寻找可以登陆这里的简单二分搜索。
github 上有一个通用的二进制搜索模块,因为标准库不提供此通用功能:https://github.com/bbp-brieuc/binarysearch
适用于 GO 1.21
slices.BinarySearch
捆绑在 Go 包中。
package main
import (
"fmt"
"slices"
)
func main() {
searchField := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
fmt.Println( slices.BinarySearch(searchField, 5) )
}
也很通用。
通用型版本! (转1.18)
时间复杂度:log2(n)+1
package main
import "golang.org/x/exp/constraints"
func BinarySearch[T constraints.Ordered](a []T, x T) int {
start, mid, end := 0, 0, len(a)-1
for start <= end {
mid = (start + end) >> 1
switch {
case a[mid] > x:
end = mid - 1
case a[mid] < x:
start = mid + 1
default:
return mid
}
}
return -1
}
完整版本,带有迭代计数器,位于 playground。
func BinarySearch(array []int, target int) int {
startIndex := 0
endIndex := len(array) - 1
midIndex := len(array) / 2
for startIndex <= endIndex {
value := array[midIndex]
if value == target {
return midIndex
}
if value > target {
endIndex = midIndex - 1
midIndex = (startIndex + endIndex) / 2
continue
}
startIndex = midIndex + 1
midIndex = (startIndex + endIndex) / 2
}
return -1
}