sorting - 无法在一片结构中搜索项目

Question

在这件事上让我大吃一惊。任何帮助将不胜感激。我创建了一个名为 Person 的结构，以及一个名为 PersonList 的自定义 slice 类型，其中包含 *Person。我能够对 slice 进行填充和排序，但是在搜索 slice 时我得到了奇怪的结果:搜索能够找到一些项目，但不能找到其他项目。

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))
}

这是输出:

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

搜索方法可以找到id的839和93420，但是找不到其他的。

有什么想法吗？非常感谢!

Answer 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 方法。

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.