問題タブ [binary-search]

実行パスで何度もヒットするバイナリ検索ループがあります。

プロファイラーは、検索の分割部分（検索範囲の高いインデックスと低いインデックスを指定して中間のインデックスを見つける）が、実際には検索の最もコストのかかる部分であり、約4倍であることを示しています。

（私は思う）効率的な二分探索では、正確な中間値を見つけることは重要ではなく、どちらの方向にもバイアスがない中央付近の値だけを見つけることが重要です。

mid = (low + high) / 2はるかに高速なものに置き換えるためのビットをいじるアルゴリズムはありますか？

編集：言語はC＃ですが、同等のビット演算はどの言語でも有効です（ただし、パフォーマンス上の利点はない場合があります）。そのため、C＃タグをオフのままにしました。

次のようなクラスとインスタンスのリストがあります (フィールド名は無実/独自のものを保護するために変更されています):

リストbloatListは によって内部的にBloatProducer保持され、新しいレコードのみを追加Bloatし、古いレコードを変更せず、各フィールドが単調に増加するように維持されます。たとえば、bloatProducer.testMonotonicity()常に が返されtrueます。

timeInMilliseconds、spaceInBytes、または costInPennies フィールドのいずれかでレコードCollections.binarySearch(list,key,comparator)を検索するために使用したいと思います。Bloat（そして、番号が2つのレコードの間にある場合、前のレコードを見つけたい）

これを機能させるために一連の 3 つの Comparator クラスを作成する最も簡単な方法は何ですか? 探していないものにダミー フィールドを持つ Bloat オブジェクトであるキーを使用する必要がありますか?

私は球のオンラインジャッジ最短経路問題を解いています。このコードのビットは私に問題を与えています：

どうすればこれを回避できNullPointerExceptionますか？

入力ファイル：

私は口述のリストを持っています、このようなもの：

dictアイテムは、データに従ってリスト内でソートされ'offset'ます。実際のデータははるかに長くなる可能性があります。

私がやりたいのは、特定のオフセット値を指定してリスト内のアイテムを検索することです。これは、正確にはそれらの値の1つではありませんが、その範囲内です。だから、二分探索は私がやりたいことです。

私は今、Pythonbisectモジュールに気づきました。これは、既成の二分探索です。すばらしいですが、この場合は直接使用できません。自分のニーズに適応する最も簡単な方法は何だろうと思ってbisectいます。これが私が思いついたものです：

それは印刷します：

私の質問は、これが私がやりたいことをするための最良の方法ですか、それとも他のもっと簡単でより良い方法がありますか？

これはしばらくの間私を悩ませてきました。二分探索木の形で配置するN個のキーが与えられた場合、作成できるツリーの可能な数は、カタラン数列のN番目の数に対応することを知っています。

私はこれがなぜであるかを決定しようとしてきました。それを直感的に説明しようとするかもしれないものを見つけることができない私はSOの集合的な知識に頼ります。可能な木の数を計算する他の方法を見つけましたが、それらは直感的ではないようで、使用方法以外の説明はありませんでした。さらに、wikiページ（上記のリンク）には、3つのキーを使用して可能な樹木形成の画像も表示されます。これにより、適切でわかりやすい説明が聞こえると思います（言うまでもなく、記事には含まれていません）。 ）。

前もって感謝します！

文字列配列 [1, 2, 3] があり、Arrays.binarySearch を使用してこれらすべての数値を検索すると、1 と 2 が見つかりますが、3 の場合は -1 が返されます。なぜそれがそのように機能するのか考えていますか? 配列/コレクションで常に検索を行うより良い代替手段は何ですか?

それで、私は二分探索についてもっと理解したいのです、なぜなら私は本当に理解していないからです。二分探索には、配列がソートされるという前提条件が必要です。正解ですか？メソッドはこの前提条件をチェックし、満たされない場合は例外をスローする必要があるようです。しかし、なぜ前提条件をチェックするのは悪い考えなのでしょうか？

これはで説明されている問題Programming pearlsです。著者が説明した二分探索法がわかりません。誰かが詳しく説明するのを手伝ってもらえますか？ありがとう。

編集：私は一般的に二分探索を理解することができます。この特殊なケースで二分探索を適用する方法がわかりません。別の番号を選択できるように、欠落している番号が特定の範囲内にあるかどうかを判断する方法。英語は私の母国語ではありません。それが著者をよく理解できない理由の1つです。だから、平易な英語を使ってください:)

編集：あなたの素晴らしい答えとコメントをありがとうございました！この質問を解決することから私が学んだ最も重要な教訓は、バイナリ検索はソートされた配列だけでなく適用されるということです！

I need a comparison function for blocks of memory for doing binary searches on arrays of bytes in the D programming language. It does not need to have any useful semantics. It only needs to be fast and be a valid comparison function (one that produces a total ordering). The blocks of memory to be compared are already known to be the same length.

C's memcmp is actually pretty slow because it tries to preserve useful string comparison semantics, which I don't need. Below is the best I've come up with so far. Does anyone know of anything better, preferably w/o dipping into non-portable CPU-specific instructions?

Edit: I've read up on SSE and I don't want to use it for 3 reasons:

1. It's not portable.
2. It requires programming in ASM.
3. The comparison instructions assume your data is floating points, which might be problematic if some data happens to match the pattern for a NaN.