3

次の例を考えてみましょう。

package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    var a sort.IntSlice
    a = append(a, 23)   
    a = append(a, 3)
    a = append(a, 10)
    sort.Sort(a)    
    fmt.Println(a)
    n = sort.SearchInts(a, 1)
    fmt.Println(n)
    n = sort.SearchInts(a, 3)
    fmt.Println(n)
}

http://play.golang.org/p/wo4r43Zghv

そして結果は次のとおりです。

[3 10 23]
0
0

最初の要素と存在しない要素の両方がインデックスとして0を返す場合、番号がスライスに存在するかどうかをどのように知る必要がありますか？

更新 インデックスはスライスの長さよりも大きくなる可能性があるため、要素がスライスに存在するかどうかを確認する適切な方法は次のとおりです。

num := 1
n = sort.SearchInts(a, num) 
if n < len(a) && a[n] == num {
  // found
}
4

4 に答える 4

3

機能的に奇妙な機能のように見えるかもしれませんが、文書化されています：

たとえば、スライスデータが昇順で並べ替えられている場合、Search（len（data）、func（i int）bool {return data [i]> = 23}）を呼び出すと、data[i]>となるような最小のインデックスiが返されます。 =23。

明らかな解決策も文書化されています：

呼び出し元が23がスライスに含まれているかどうかを確認する場合は、data [i]==23を個別にテストする必要があります。

于 2013-01-21T10:41:32.650 に答える
1

探していた番号が実際に返されたインデックスに存在するかどうかを確認します。の二分探索ルーチンはsort、値がまだ存在しない場合に値を挿入できるインデックスを見つけることになっています。

たとえば、例のスライスで100を検索すると、値をスライスに追加する必要があるため、3が返されます。

呼び出しSearch(len(data), func(i int) bool { return data[i] >= 23 })は、のような最小のインデックスiを返しますdata[i] >= 23。発信者が23がスライスに含まれているかどうかを確認したい場合は、data[i] == 23個別にテストする必要があります。

于 2013-01-21T10:38:38.487 に答える
1

SearchIntsソートされたintのスライスでxを検索し、Searchで指定されたインデックスを返します。SearchInts関数を使用した呼び出しSearch：

func(i int) bool { return a[i] >= x }

検索ドキュメントからの引用：

検索では、バイナリ検索を使用して、[0、n）でf（i）が真になる最小のインデックスiを見つけて返します。ただし、範囲[0、n）で、f（i）== trueはf（i + 1）==true。つまり、検索では、fが入力範囲[0、n）の一部の（おそらく空の）プレフィックスに対してfalseであり、次に（おそらく空の）余りに対してtrueである必要があります。検索は最初の真のインデックスを返します。そのようなインデックスがない場合、検索はnを返します。検索では、[0、n）の範囲のiに対してのみf（i）が呼び出されます。

したがって、基本的には、スライスがソートされたままになるように、検索した番号を挿入する必要があるインデックスが返されます。

返されたインデックスで、スライス内の番号が検索した番号と同じであるかどうかを確認してください。

于 2013-01-21T10:41:29.190 に答える
1

このスニペットはドキュメントからのものです：

x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
    // x is present at data[i]
} else {
    // x is not present in data,
    // but i is the index where it would be inserted.
}

http://golang.org/pkg/sort/#Search

だからあなたはi < len(data) && data[i] == xあなたが提案するようにチェックしなければなりません。

于 2013-01-22T14:03:10.697 に答える