Go语言 排序包中的BinarySearch

m3eecexj  于 2023-09-28  发布在  Go
关注(0)|答案(2)|浏览(92)

我在Go sort包”func SearchInts(a []int, x int) int“中查看这个函数,并好奇是否有一种直接的方法来识别切片中是否存在元素?
在Java数组中,binarySearch(..)只返回一个负值。我很好奇如果x不存在,golang的API func SearchInts(a []int, x int)是否会报告?不知道为什么func SearchInts(a []int, x int)不返回两个值(index,isPresent)

dwbf0jvd

dwbf0jvd1#

您可以简单地检查:

i := sort.SearchInts(slice, value)
if i<len(slice) && slice[i]==value {
   // It exists
}
fhg3lkii

fhg3lkii2#

我没有使用你提到的函数,但是根据包的官方文档,SearchInts函数在一个排序的int切片中搜索x,并返回Search指定的索引。
因此,基于文档中提供的示例,对于如下内容:

package main

import (
    "fmt"
    "sort"
)

func main() {
    a := []int{1, 2, 3, 4, 6, 7, 8}

    x := 2
    i := sort.SearchInts(a, x)
    fmt.Printf("found %d at index %d in %v\n", x, i, a)

    x = 5
    i = sort.SearchInts(a, x)
    fmt.Printf("%d not found, can be inserted at index %d in %v\n", x, i, a)
}

您将得到以下输出:

found 2 at index 1 in [1 2 3 4 6 7 8]
5 not found, can be inserted at index 4 in [1 2 3 4 6 7 8]

幸运的是,从GO的最新版本1.21开始,有一个新的slices包可用,其中包括BinarySearch函数,它的行为类似于您希望从Java中获得的(如果找到值,则返回bool类型)。

package main

import (
    "fmt"
    "slices"
)

func main() {
    names := []string{"Alice", "Bob", "Vera"}
    n, found := slices.BinarySearch(names, "Vera")
    fmt.Println("Vera:", n, found)
    n, found = slices.BinarySearch(names, "Bill")
    fmt.Println("Bill:", n, found)
}

Output:

Vera: 2 true
Bill: 1 false

根据文件:BinarySearch在排序后的切片中搜索target,并返回找到target的位置,或target在排序顺序中出现的位置;它还返回一个bool,说明目标是否真的在切片中找到。切片必须按升序排序。
根据您的需要进行调整,您可以在计算条件时跳过int返回值,而只使用bool值。举例来说:

package main

import (
    "fmt"
    "slices"
)

func main() {
    names := []string{"Alice", "Bob", "Vera"}
    if _, found := slices.BinarySearch(names, "Bob"); found {
        fmt.Println("Bob:", found)
    }
}

这将产生以下输出:

Output:

Bob: true

此外,这个函数使用泛型下划线,所以它不仅适用于int类型,还适用于任何其他类型。
最后但并非最不重要的是,还有一个BinarySearch函数的替代版本,它允许您在BinarySearchFunc上使用自己的比较函数。如果你需要一些自定义的比较逻辑,这可能对你也很有用。
您可以在https://tip.golang.org/doc/go1.21上查看GO v1.21的完整发行说明,以防您想深入了解。

相关问题