英文:
not able to search for an item in a slice of structs
问题
这段代码中的问题在于 Search 方法的实现。在 Search 方法中，使用了 sort.Search 函数来查找元素的索引，但是该函数要求切片是已排序的。然而，在你的代码中，Search 方法被调用之前并没有调用 Sort 方法对切片进行排序，所以结果是不可预测的。
要解决这个问题，你可以在调用 Search 方法之前先调用 Sort 方法对切片进行排序，确保切片是有序的。修改代码如下：
func main() {
// ...
plist.Sort()
fmt.Printf("plist=%v\n", plist)
fmt.Printf("3=%d\n", plist.Search(3))
fmt.Printf("23=%d\n", plist.Search(23))
fmt.Printf("839=%d\n", plist.Search(839))
fmt.Printf("7238=%d\n", plist.Search(7238))
fmt.Printf("93420=%d\n", plist.Search(93420))
}
这样修改之后，Search 方法就能正确地找到所有的元素了。希望能对你有所帮助！
英文:
Pulling my hair out on this one. Any help would be greatly appreciated. I've created a struct called Person, and a custom slice type called PersonList that holds *Person. I'm able to populate and sort the slice, but when it comes to searching the slice I'm getting weird results: search is able to find some items, but not others.
type Person struct {
id int
name string
}
type PersonList []*Person
func (pl *PersonList) Add(p *Person) {
*pl = append(*pl, p)
}
func (pl PersonList) Search(id int) int {
f := func(i int) bool { return pl[i].id == id }
return sort.Search(len(pl), f)
}
func (pl PersonList) Sort() {
sort.Sort(pl)
}
func (pl PersonList) IsSorted() bool {
return sort.IsSorted(pl)
}
func (pl PersonList) Len() int {
return len(pl)
}
func (pl PersonList) Swap(i, j int) {
pl[i], pl[j] = pl[j], pl[i]
}
func (pl PersonList) Less(i, j int) bool {
return pl[i].id < pl[j].id
}
func (p Person) String() string {
return "id=" + strconv.Itoa(p.id) + " name=" + p.name + "\n"
}
func main() {
plist := make(PersonList, 0)
plist.Add(&Person{839, "Bob"})
plist.Add(&Person{23, "Larry"})
plist.Add(&Person{93420, "Jane"})
plist.Add(&Person{3, "Sam"})
plist.Add(&Person{7238, "Betty"})
fmt.Printf("plist=%v\n", plist)
plist.Sort()
fmt.Printf("plist=%v\n", plist)
fmt.Printf("3=%d\n", plist.Search(3))
fmt.Printf("23=%d\n", plist.Search(23))
fmt.Printf("839=%d\n", plist.Search(839))
fmt.Printf("7238=%d\n", plist.Search(7238))
fmt.Printf("93420=%d\n", plist.Search(93420))
}
And here is the output:
plist=[id=839 name=Bob
id=23 name=Larry
id=93420 name=Jane
id=3 name=Sam
id=7238 name=Betty
]
plist=[id=3 name=Sam
id=23 name=Larry
id=839 name=Bob
id=7238 name=Betty
id=93420 name=Jane
]
3=5
23=5
839=2
7238=5
93420=4
The search method was able to find id's 839 and 93420, but couldn't find the others.
Any ideas? Thanks very much!
答案1
得分: 1
例如，
package main
import (
"fmt"
"sort"
"strconv"
)
type Person struct {
id int
name string
}
type PersonList []*Person
func (pl *PersonList) Add(p *Person) {
*pl = append(*pl, p)
}
func (pl PersonList) Search(id int) int {
f := func(i int) bool { return pl[i].id >= id }
if i := sort.Search(len(pl), f); pl[i].id == id {
return i
}
return -1
}
func (pl PersonList) Sort() {
sort.Sort(pl)
}
func (pl PersonList) IsSorted() bool {
return sort.IsSorted(pl)
}
func (pl PersonList) Len() int {
return len(pl)
}
func (pl PersonList) Swap(i, j int) {
pl[i], pl[j] = pl[j], pl[i]
}
func (pl PersonList) Less(i, j int) bool {
return pl[i].id < pl[j].id
}
func (p Person) String() string {
return "id=" + strconv.Itoa(p.id) + " name=" + p.name + "\n"
}
func main() {
plist := make(PersonList, 0)
plist.Add(&Person{839, "Bob"})
plist.Add(&Person{23, "Larry"})
plist.Add(&Person{93420, "Jane"})
plist.Add(&Person{3, "Sam"})
plist.Add(&Person{7238, "Betty"})
fmt.Printf("plist=%v\n", plist)
plist.Sort()
fmt.Printf("plist=%v\n", plist)
fmt.Printf("3=%d\n", plist.Search(3))
fmt.Printf("23=%d\n", plist.Search(23))
fmt.Printf("839=%d\n", plist.Search(839))
fmt.Printf("7238=%d\n", plist.Search(7238))
fmt.Printf("93420=%d\n", plist.Search(93420))
}
输出：
plist=[id=839 name=Bob
id=23 name=Larry
id=93420 name=Jane
id=3 name=Sam
id=7238 name=Betty
]
plist=[id=3 name=Sam
id=23 name=Larry
id=839 name=Bob
id=7238 name=Betty
id=93420 name=Jane
]
3=0
23=1
839=2
7238=3
93420=4
我修复了你的 PersonList 的 Search 方法。
func Search(n int, f func(int) bool) intSearch 使用二分查找在范围 [0, n) 中找到并返回最小的满足 f(i) 为 true 的索引 i，假设在范围 [0, n) 上，f(i) == true 意味着 f(i+1) == true。也就是说，Search 要求 f 在输入范围 [0, n) 的某个（可能为空）前缀上为 false，然后在（可能为空）剩余部分上为 true；Search 返回第一个 true 的索引。如果没有这样的索引，Search 返回 n。（注意，与例如 strings.Index 不同，“未找到”返回值不是 -1）。Search 仅在范围 [0, n) 中的 i 调用 f(i)。
Search 的常见用法是在排序的可索引数据结构（如数组或切片）中找到值 x 的索引 i。在这种情况下，参数 f（通常是一个闭包）捕获要搜索的值，以及数据结构的索引和排序方式。
例如，给定一个按升序排序的切片 data，调用 Search(len(data), func(i int) bool { return data[i] >= 23 }) 返回最小的索引 i，使得 data[i] >= 23。如果调用者想要确定 23 是否在切片中，它必须单独测试 data[i] == 23。
对于按降序排序的数据，应该使用 <= 运算符而不是 >= 运算符。
英文:
For example,
package main
import (
"fmt"
"sort"
"strconv"
)
type Person struct {
id int
name string
}
type PersonList []*Person
func (pl *PersonList) Add(p *Person) {
*pl = append(*pl, p)
}
func (pl PersonList) Search(id int) int {
f := func(i int) bool { return pl[i].id >= id }
if i := sort.Search(len(pl), f); pl[i].id == id {
return i
}
return -1
}
func (pl PersonList) Sort() {
sort.Sort(pl)
}
func (pl PersonList) IsSorted() bool {
return sort.IsSorted(pl)
}
func (pl PersonList) Len() int {
return len(pl)
}
func (pl PersonList) Swap(i, j int) {
pl[i], pl[j] = pl[j], pl[i]
}
func (pl PersonList) Less(i, j int) bool {
return pl[i].id < pl[j].id
}
func (p Person) String() string {
return "id=" + strconv.Itoa(p.id) + " name=" + p.name + "\n"
}
func main() {
plist := make(PersonList, 0)
plist.Add(&Person{839, "Bob"})
plist.Add(&Person{23, "Larry"})
plist.Add(&Person{93420, "Jane"})
plist.Add(&Person{3, "Sam"})
plist.Add(&Person{7238, "Betty"})
fmt.Printf("plist=%v\n", plist)
plist.Sort()
fmt.Printf("plist=%v\n", plist)
fmt.Printf("3=%d\n", plist.Search(3))
fmt.Printf("23=%d\n", plist.Search(23))
fmt.Printf("839=%d\n", plist.Search(839))
fmt.Printf("7238=%d\n", plist.Search(7238))
fmt.Printf("93420=%d\n", plist.Search(93420))
}
Output:
plist=[id=839 name=Bob
id=23 name=Larry
id=93420 name=Jane
id=3 name=Sam
id=7238 name=Betty
]
plist=[id=3 name=Sam
id=23 name=Larry
id=839 name=Bob
id=7238 name=Betty
id=93420 name=Jane
]
3=0
23=1
839=2
7238=3
93420=4
I fixed your PersonList Search method.
> Package sort
>
> func Search
>
> func Search(n int, f func(int) bool) int
>
> Search uses binary search to find and return the smallest index i in
> [0, n) at which f(i) is true, assuming that on the range [0, n), f(i)
> == true implies f(i+1) == true. That is, Search requires that f is false for some (possibly empty) prefix of the input range [0, n) and
> then true for the (possibly empty) remainder; Search returns the first
> true index. If there is no such index, Search returns n. (Note that
> the "not found" return value is not -1 as in, for instance,
> strings.Index). Search calls f(i) only for i in the range [0, n).
>
> A common use of Search is to find the index i for a value x in a
> sorted, indexable data structure such as an array or slice. In this
> case, the argument f, typically a closure, captures the value to be
> searched for, and how the data structure is indexed and ordered.
>
> For instance, given a slice data sorted in ascending order, the call
> Search(len(data), func(i int) bool { return data[i] >= 23 }) returns
> the smallest index i such that data[i] >= 23. If the caller wants to
> find whether 23 is in the slice, it must test data[i] == 23
> separately.
>
> Searching data sorted in descending order would use the <= operator
> instead of the >= operator.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论