弟さんはいますか.Go標準ライブラリの二分検索にバグがあるのではないかと疑っています.

「弟さんはいますか.Go標準ライブラリの2点がバグを探しているのではないかと疑っています.」
「お兄さん、慌てないで、ソースの前に秘密はありません.座って私の吹き飛ばしを聞いてください.c++の牛が追い詰める.の"
次のGoコード、indexの結果はいくらだと思いますか?

arr := []int{1, 3, 5, 7}
index := sort.Search(len(arr), func(i int) bool {
    return arr[i] == 3
})

indexの結果は1ではなく4です.(えっと、戻る4は何の鬼なのか、見つけたら返すべきではないか、見つからないなら-1に戻るべきではないか)
私たちの映像の2点はこうです.

while (low <= high) {
    mid := (low + high) / 2
    if arr[mid] < target {
        low = mid + 1
    } else if arr[mid] > target {
        high = mid - 1
    } else {
        return mid
    }
}

標準ライブラリのsort.Searchはこうです

func Search(n int, f func(int) bool) int {
    i, j := 0, n
    for i < j {
        h := int(uint(i+j) >> 1)
        if !f(h) {
            i = h + 1
        } else {
            //       
            j = h
        }
    }
    return i
}

ちょっと見てSearchは二分検索の実装のようだ.
しかし、ユーザが入力した比較関数fがtrueを返して検索を終了するのではなく、現在の[i, j)区間の前半で検索を継続する.
また、fがfalseである場合も、現在の要素と検索する要素のサイズ関係を比較するのではなく、直接後半で検索する.
forループ終了の唯一の条件はi >= jである.
後の文は説明を便利にするために、名詞を統一します.targetは、検索する値、すなわち上の3を表す.
私たちはまず正しい使い方を貼って、それから分析します.

index := sort.Search(len(arr), func(i int) bool {
    // return arr[i] == 3
    return arr[i] >= 3
})

関数fは、ユーザに== targetのルールを指定させるのではなく、上位と下位の組み合わせである.
現在の要素< targetであれば、必然的に現在の要素より前の要素も< target(昇順配列であるため)であるため、後半のみで検索される.
現在の要素>= targetは、現在の要素の前の要素とtargetのサイズが不確定である.現在のエレメントの後のエレメントも、必ず>または== targetである.この場合、Searchは前半だけ探します.
よく考えてみると、この検索方法にはいくつかのメリットがあります.

複数の要素がtargetに等しい場合、実際には下付きの最小要素

を見つけることができる.

targetが存在しない場合、返される下付き記号は、targetを挿入する場合、挿入位置(挿入後も配列秩序を保つ)

を識別する.

このプログラミングパターンに基づいて、上位層は、自身のデータ型に関連する比較関数

を1つだけ提供する.
sort.Search戻り値の正しい食べ方:indexがlenの範囲内であると判断し、index位置の要素の値が検索したい値と等しいindex < len(arr) && arr[index] == target、条件が満たされれば説明が見つかり、戻ってくるのは下付き、条件が満たさなければ説明が見つからず、戻ってくるのは挿入可能な位置である.
また、上記の例では、配列は昇順に並べ替えられ、配列が降順である場合、関数fは<=を使用するべきである.
また、sort.Searchにはもう一つの小さな詳細があります.h := int(uint(i+j) >> 1)です.ここではuint加算に変換してから半分を取り、2つのint加算オーバーフローを防ぐことができます.
アルゴリズムの部分は更に1つ多く言って、実際に関数fと関数Searchは1つの完全なアルゴリズムの論理で、ただAPIは抽象を提供するために、強引に論理を切断して、もしあなたは前にこのような二分アルゴリズムの思想に接触したことがないならば、Searchの実現だけを見て、関数fの現実を見ないで、確かに少し気絶しやすいです.
ここで、アルゴリズムの部分は終わりました.次に、Goとc++のプログラミングパターンについて話します.つまり、データ型を抽象化し、APIを提供する方法について話します.
sort.Searchの関数fは,タイプに関連する配列のみをパラメータとして受信するのではなく,下位パラメータのみを受信するコールバック関数と見なすことができ,上位提供関数fの実装では,外層の配列変数を直接用い,実際にはGo閉パケットの特性を用いた.
では、私はいくつかの基礎タイプ向けの検索関数を直接提供したいと仮定して、上層から関数fを提供しませんか?実際にsortパッケージは本当に提供されています.

// -          target
// -   ，             
func SearchInts(a []int, x int) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

func SearchFloat64s(a []float64, x float64) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}
func SearchStrings(a []string, x string) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

しかし、関数fの実装には配列にアクセスする必要があり、演算子>=の比較を行う必要があるため、すなわち配列のタイプを知る必要があり、すなわち上層に提供される関数も具体的なタイプの配列に伝達しなければならないため、sortパケットは3つの基礎タイプ向けの関数を提供し、関数の署名を見ると、スライスタイプが異なるだけで、中の実装はそっくりである.
他の基礎タイプなら、int 64、float 32など、合わない、ありません.欲しい?ctrl+cvに続きます.
また,Goは関数リロードをサポートしていないため,この3つの関数名は同じではなく,接尾辞を付けなければならない.
sortパッケージは、上層部の別の使用方法にも提供されます.

type IntSlice []int
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }

この方法では、メソッド名は同じですが、パラメータのタイプが異なり、署名が一致していないため、同じtype xxx interfaceに適していません.そして、あなたにも3つしか書いていません.の
事実上、Goはinterface{}に基づいてタイプを抽象化し、統一インタフェースを提供し、内部でタイプを判断することができる.しかし、この方法では実行時のオーバーヘッドが増加します.
最後に、c++標準ライブラリSTLの2点検索インタフェースの設計を見てみましょう.std::binary_search関数は次のように宣言されます.

template 
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);

template 
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

関数の再ロードによって、2つの関数が提供されていることがわかります.
関数のリロードは文法糖で、コンパイル時に異なる関数が生成されますが、コードを書く人には感知されません.
まず,c++はテンプレート手法により,比較演算子をサポートするすべての基礎タイプがこの関数を直接使用できることを見た.また、非ベースタイプは、比較演算子を再ロードすることによって、最初の関数を直接使用することもできます.
テンプレートは、コンパイル時にテンプレートと特定のタイプのテンプレートを使用するコードからテンプレートに対応する特定のコードを生成します.
演算子のリロードは、カスタムタイプに演算子メンバー関数を追加し、カスタムタイプが演算子演算を直接使用できるようにします.
2番目の関数は、実際には別の手段を提供し、上位層は特定のタイプの比較関数compを指定することができる.
コード量にしても、実行効率にしても、個人的にはc++のほうが好きです.
本明細書に関連するテストコード:https://github.com/q191201771...
最後に、読んでくれてありがとう~
本文は終わって、作者のyoko、労働人民の成果を尊重して、転載して原文の出所を明記してください:https://pengrl.com/p/20011/本の文章は1文の多発プラットフォームのArtiPubから自動的に発表します