問題タブ [binary-search]

binary_range_search私は次のように呼ばれる関数を持っています：

brs_iterator->()$rangeがオーバーラップするすべての@$rangeを繰り返し処理します。

binary_range_search複数の範囲をターゲットとして呼び出すことができるように拡張したいと思います。例：

したがって、$ range-> [0]の検索が終了すると、$range->[1]などに移動する必要があります。問題の関数は、元の形式で次のようになります。

重複する範囲が見つかるまで、これは標準の二分探索戦略です。次に、それは右に移動し、それを使い果たし、左に動き、それを使い果たし、そして最後に諦めます。理想的には、それはおそらくshift次のターゲット範囲であり、検索をやり直す必要があります（おそらく再帰を介して？）。私の問題は、イテレータ構造でそれを機能させる方法がわからないことです。

キーと値の両方を使用してBSTを実装する必要がありますか？次のようなメソッド呼び出しを持つBSTを実装できます。この場合、V値に基づいて、トラバーサルを左ノードと右ノードのどちらに移動するかを各ノードで比較します。

または、次のようなメソッド呼び出しを持つようにBSTを実装できます。ここで、Kキーは、左ノードと右ノードのどちらにトラバースするかを比較して決定します。

ブラウザーでデプロイされた Flash アプリ (SQLConnection にアクセスできる AIR アプリではない) があり、HTTPService を介してリモート サーバーから JSON 結果をフェッチします。

返された結果セット (オブジェクトの配列) からサブセットを効率的に抽出する必要があります。クラウドを介したバックエンドへの複数の呼び出しは機能しません。それはすべてクライアント側で発生する必要があります。

Array sortOnメソッドのように、すべてのオブジェクトが共通に持っているプロパティの 1 つによってオブジェクトの配列を並べ替えることができる Flex ActionScript のコレクション クラスはありますか?配列内のすべての項目にアクセスして比較することなく、配列のバージョンを取得しますか?

たとえば、オブジェクトの配列があり、各オブジェクトにzipプロパティとnameプロパティがある場合、コピーが並べ替えられた元の配列のコピーから、zip = 10015 のすべてのオブジェクトを抽出できるようにしたいと考えています。ジップ。

ありがとう

JavaScript で文字列のバイナリ検索を行う関数を最適化しようとしています。

==二分探索では、キーがピボットかピボットかを知る必要があります<。

ただし、JavaScript では 2 つの文字列比較が必要です。これは、 (より小さい、等しい、より大きい) の3 つの値を返す関数Cを持つ同様の言語とは異なります。strcmp()(-1, 0, +1)

二分探索の各反復で 1 つの比較のみが必要になるように、3 値を返すことができる JavaScript のようなネイティブ関数はありますか?

ウィキペディアから：

ソートされたリストの実装: スーパーマーケットのレジの列のように、重要な人々が重要でない人々の前で「カット」する場所。( O(n) の挿入時間、O(1) の get-next 時間、O(n*log(n)) のビルド)

二分探索アルゴリズムで挿入位置を検索すると、挿入時間の複雑さは O(log(n)) になるはずです。ここでは、ジョブの到着順序を優先順位の要素として扱います。

それで、私は間違っていますか、それともウィキペディアは間違っていますか?

更新:TAOCP のリストの厳密な定義によると:

線形リストは、n >=0 のノード X 1、X[2]、...、X[n] のシーケンスであり、その基本的な構造特性には、アイテムが行に表示されるときのアイテム間の相対位置のみが含まれます。

ウィキペディアの参照リストはlinked-listではなく、 arrayである可能性があると思います。

ありがとう。

https://docs.oracle.com/javase/1.5.0/docs/api/java/util/Arrays.html

Sunは、二分探索の実装の複雑さについては言及していません。これは間違いですか？私はそれがそうあるべきであることを知っていますO(logn)、しかし彼らがこれを明確に述べていないときそれは私を緊張させます。それらは、Arrays.sortのようないくつかのアルゴリズムに対して行います。

実際の実装について知っている人はいますか？私はまだ自分でソースコードをダウンロードする機会がありませんでした！些細な二分探索だと思いますが、Sunはパフォーマンスを向上させるためにアルゴリズムを微調整することがあります。

二分探索木での順序通りの走査（VISIT LEFT、VISIT ROOT、VISIT RIGHT）により、ソートされた結果が得られることを知っています。しかし、バイナリツリーでポストオーダートラバーサル（VISIT LEFT、VISIT RIGHT、VISIT ROOT）を実行する必要があり、その結果、ソートされた値が得られるはずです。

それを達成するために、どのように二分木を構築する必要がありますか？

BSTのコードをいくつか見てきましたが、各ノードが構造体であることがわかります。これは必要ですか？

二分探索アルゴリズムでは、上限要素はarray.length-1です。配列の最後の要素を見つけるにはどうすればよいですか？

長さ8の配列の要素の下限と上限がそれぞれ6と7の場合、私の中間要素は次のようになります。

mid =（6 + 7）/ 2、つまりJavaでは6