問題タブ [binary-search]

ソートされたベクトルに格納されているデータがあります。このベクトルは、いくつかのキーでソートされています。STL には、要素がこのソートされたリストにあるかどうかをチェックするアルゴリズムがあることを知っています。これは、次のように書くことができることを意味します。

ただし、「thingToSearchFor」オブジェクトの構築はエレガントではありません。より良い方法はありますか？これに似た何か？

引数として渡す特定の値よりも大きい並べ替えられたリストの最初の数値を見つける関数を Python で作成しようとしています。これを達成するために単純なリスト内包表記を使用する例をオンラインで見つけましたが、私の目的のためには、この操作を頻繁に大きなリストで実行する必要があるため、線形時間で実行される検索はコストがかかりすぎます。

これを達成するために反復二分探索のような関数を書くことにクラックがありましたが、それが正しく機能しないいくつかのエッジケースに出くわしています。ちなみに、リストに大きな項目がない場合は、この関数は必要ありません。ここに私の既存の機能があります：

この関数が機能しない 1 つのケースは次のとおりです。

ここで正しい結果は になります262140。これは、リスト内の より大きい最初の数値だから262139です。

実際に機能するこれのよりクリーンな実装を推奨できる人はいますか? これがそれほど難解な問題になるとは思いませんでしたが、まだ解決策を見つけることができませんでした。

私はいつも得る-3。問題は にあり"Name"ます。"Name"配列に入れられないのはなぜですか? 何か案が？

targetリストまたはタプル内の値、、のバイナリ検索を実行するために、次のコードを記述しましたcollection。

ご覧のとおり、にtargetが見つからない場合collection、関数は-1を返します。私が何をしたかに関係なく、関数は-1を返しました。

この問題の原因は何ですか？

私のAndroidアプリでは、オートコンプリート付きの入力フィールドが必要です。アイテムの数は約300000になります。最善の解決策は、アイテムをファイル（sdcard上）に入れることです。1行に1つのアイテムがあり、各行の文字数は同じであるため、特定の行番号を探すことができます。 。ユーザーがテキストフィールドに何かを入力すると、ファイルを（RandomAccessFileを介して）バイナリ検索し、提案を表示します。

オートコンプリートを超高速（理想的には100ミリ秒未満ですが、不可能だと思います）にしたいのですが、どのような最適化を実行できますか？

更新1： ユーザー入力をスペース付きの小文字の英語文字（az）に変換します。したがって、「A/b」は「ab」に変換されてから検索されます。

Uodate 2： 単語の先頭の部分文字列を検索するために、追加のものが必要であることに気付きました。

二分探索を使用して、負でない入力整数の平方根 (最も近い整数に切り捨て) を再帰的に計算するプログラムを作成するのに助けが必要です。

これは私がこれまでに持っているものです:

平方根を計算するためにバイナリ検索を使用する必要があるという事実は、私を混乱させている部分です。これを行う方法について誰か提案があれば、大歓迎です。ありがとうございました

-これは、バイナリ検索アルゴリズムを使用した私のfind（）メソッドです。

• 期待どおりに機能します。全く問題ありません。

  /li>

これが線形検索を使用した元のinsert（）メソッドです。かなり簡単ですよね？

find（）メソッドのバイナリ検索アルゴリズムを使用するようにinsert（）メソッドを変更する必要があります。これが私がこれまでに思いついたものです。明らかに何か問題がありますが、問題を見つけることができないようです。まったく機能しません。つまり、挿入は実行されません。

言語：Java

順序付き配列を使用します。

私はこのようなコンテナを持っています:

time の前に最後のデータ オブジェクトを取得したい場合はt、ダミー オブジェクトを作成して を呼び出すことができますupper_bound()。

これにより、対数検索が複雑になります。
不器用に見えることは別として、このようなダミーオブジェクトを作成するのが非常に難しい場合、このアプローチには問題があります (実行時のパフォーマンスではなく、コーディングの手間がかかります)。

私は見ましたstd::multiset::key_compが、それをどのように使用できるかわかりません..
両方ともstd::multiset::find()、コンテナの、つまりオブジェクトstd::binary_search()を提供してほしい...key_typeTimeSortableData

ダミー オブジェクトを作成せずに効率的に検索するにはどうすればよいですか?

コメントからの更新:
もあります:find_if()ダミー オブジェクトを作成する手間を省きますが、O(n) の複雑さを犠牲にします。

次のコードの何が問題になっていますか? 二分探索の私の実装を使用して手紙が見つからないのはなぜですか?

Perlで二分探索アルゴリズムを実装したいと思います。私の「配列」は降順でソートされています（実際の配列ではなく、インデックスを取得して値を返す関数）。問題は、同じ値の範囲が存在する可能性があることです。検索した値がこのように広がっている場合は、それを含む最初のインデックスを返したいと思います。

これは私が書いたものです：

これはそれを使用するための簡単な例です：

問題は、私の最後の（でマークされた## SEE MY QUESTION BELOW ##）が「きれい」かどうかわからないことです。それを行うためのより良い方法はありますか？