1

把我的头发拉出来。任何帮助将不胜感激。我创建了一个名为 Person 的结构，以及一个名为 PersonList 的自定义切片类型，其中包含 *Person。我可以对切片进行填充和排序，但是在搜索切片时，我得到了奇怪的结果：搜索能够找到一些项目，但不能找到其他项目。

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，但找不到其他的。

有任何想法吗？非常感谢！

4

1 回答 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) int

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

Search 的一个常见用途是在排序的、可索引的数据结构（例如数组或切片）中查找值 x 的索引 i。在这种情况下，参数 f（通常是闭包）捕获要搜索的值，以及数据结构的索引和排序方式。

例如，给定一个按升序排序的切片数据，调用 Search(len(data), func(i int) bool { return data[i] >= 23 }) 返回最小索引 i 使得 data[i] > = 23。如果调用者要查找23是否在切片中，则必须单独测试data[i] == 23。

搜索按降序排序的数据将使用 <= 运算符而不是 >= 运算符。

于 2013-09-01T02:39:58.013 回答