英文:
Handle not found when searching string in slice
问题
根据这个基于sort包的相当简单的代码。@JimB指出，o1的响应索引无效，因为二分查找需要使用大于或等于运算符。
l := []string{"o1", "o2", "o3"}
i1 := sort.Search(len(l), func(i int) bool { return strings.EqualFold(l[i], "o1") })
fmt.Println("o1:", i1) // 输出 3 - 错误
工作的解决方案是：
l := []string{"o1", "o2", "o3"}
i1 := sort.Search(len(l), func(i int) bool { return l[i] >= "o1" })
fmt.Println("o1:", i1)
然而，仍然需要注意一个重要的最后检查。返回值是要插入x的索引，这意味着你可能会得到类似以下的结果：
o1: 0 (索引 0)
o2: 1
o3: 2
o777: 0 (相同的索引0！)
因此，正如@JimB指出的那样，重要的是单独检查data[i] == x。
if i < len(data) && data[i] == x {
// x 存在于 data[i]
} else {
// ...
}
英文:
Based on this fairly simple code based on the sort package. The response index of o1 is invalid as pointed by @JimB because a bigger or equals operator is required for binary search
l := []string{"o1", "o2", "o3"}
i1 := sort.Search(len(l), func(i int) bool { return strings.EqualFold(l[i], "o1") })
fmt.Println("o1:", i1) //PRINTS 3 - WRONG
https://play.golang.org/p/nUs-ozTYsY
The working solution is:
l := []string{"o1", "o2", "o3"}
i1 := sort.Search(len(l), func(i int) bool { return l[i] >= "o1" })
fmt.Println("o1:", i1)
https://play.golang.org/p/WRsijy_xzV
However this still it's important to bare in mind a important last check. The return value is the index to insert x, which means that you can end up with something like:
o1: 0 (index 0)
o2: 1
o3: 2
o777: 0 (Same 0 index!)
Therefore it's important as pointed by @JimB to check for data[i] == 23 separately.
if i < len(data) && ---> data[i] == x <--- {
x is present at data[i]
} else {
...
}
答案1
得分: 3
二分查找需要进行大于或小于的比较，否则它只会在切片上进行线性搜索。为了使搜索方法能够向后扫描以寻找最小的索引，任何大于所请求索引处的值的比较都需要为真。
请参阅 sort 包中字符串搜索函数的默认实现：
https://golang.org/src/sort/search.go?s=3673:3717#L91
func SearchStrings(a []string, x string) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
英文:
A binary search requires a greater than or less than comparison, otherwise it would just be a linear search over the slice. Any comparison greater than the value at the requested index needs to be true, in order for the search method to scan backwards looking for the smallest index.
See the default implementation of the string search function from the sort package:
https://golang.org/src/sort/search.go?s=3673:3717#L91
func SearchStrings(a []string, x string) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论