3

考虑以下示例：

package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    var a sort.IntSlice
    a = append(a, 23)   
    a = append(a, 3)
    a = append(a, 10)
    sort.Sort(a)    
    fmt.Println(a)
    n = sort.SearchInts(a, 1)
    fmt.Println(n)
    n = sort.SearchInts(a, 3)
    fmt.Println(n)
}

http://play.golang.org/p/wo4r43Zghv

结果是：

[3 10 23]
0
0

当第一个元素和不存在的元素都返回 0 作为索引时，我应该如何知道切片中是否存在数字？

更新 请注意，索引也可以大于切片的长度，因此查找切片中是否存在元素的正确方法是：

num := 1
n = sort.SearchInts(a, num) 
if n < len(a) && a[n] == num {
  // found
}
4

4 回答 4

3

这似乎是一个功能上奇怪的功能，但它已记录在案：

例如，给定一个按升序排序的切片数据，调用 Search(len(data), func(i int) bool { return data[i] >= 23 }) 返回最小索引 i 使得 data[i] > = 23。

还记录了明显的解决方案：

如果调用者要查找 23 是否在切片中，则必须单独测试 data[i] == 23。

于 2013-01-21T10:41:32.650 回答
1

检查您要查找的数字是否实际存在于返回的索引中。中的二进制搜索例程sort应该找到可以插入值的索引，如果它不存在的话。

例如，在示例中的切片中搜索 100将返回 3，因为该值必须附加到切片中。

该调用Search(len(data), func(i int) bool { return data[i] >= 23 })返回最小索引 i 使得data[i] >= 23. 如果调用者要查找 23 是否在切片中，则必须data[i] == 23单独测试。

于 2013-01-21T10:38:38.487 回答
1

此片段来自文档：

x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
    // x is present at data[i]
} else {
    // x is not present in data,
    // but i is the index where it would be inserted.
}

http://golang.org/pkg/sort/#Search

所以你必须按照i < len(data) && data[i] == x你的建议进行检查。

于 2013-01-22T14:03:10.697 回答
1

SearchInts在排序的整数切片中搜索 x 并返回Search指定的索引。使用函数SearchInts调用：Search

func(i int) bool { return a[i] >= x }

引用搜索文档：

搜索使用二分搜索来查找并返回 [0, n) 中 f(i) 为真的最小索引 i，假设在 [0, n) 范围内，f(i) == true 意味着 f(i+ 1) == 真。也就是说，搜索要求 f 对于输入范围 [0, n) 的某些（可能为空）前缀为假，然后对（可能为空）余数为真；搜索返回第一个真正的索引。如果没有这样的索引，Search 返回 n。搜索仅对 [0, n) 范围内的 i 调用 f(i)。

所以基本上你会得到一个索引，你搜索的数字应该被插入，所以切片保持排序。

只需检查在返回的索引中切片中的数字是否与您搜索的数字相同。

于 2013-01-21T10:41:29.190 回答