CODEWITHSUNDEEP
sortingsearchgoslice
user2736464
user2736464

Reputation: 111

not able to search for an item in a slice of structs

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!

Upvotes: 1

Views: 84

Answers (1)

peterSO
peterSO

Reputation: 166569

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.

Upvotes: 1

Related Questions