問題タブ [binary-search]

静的/グローバル変数を使用せずに、バイナリ検索ツリーでk番目に小さい要素を見つける必要があります。それを効率的に達成する方法は？私が考えている解決策は、O（n）で操作を行うことです。これは、ツリー全体を順番にトラバースすることを計画しているため、最悪のケースです。しかし、ここではBSTプロパティを使用していないように感じます。私の仮定の解決策は正しいですか、それともより良い解決策がありますか？

並べ替えられた Book オブジェクトの配列に対してバイナリ検索を実行しようとしています。

一部のオブジェクトでは正しい結果が返されますが、すべてではありません。

私は紙の上でループを調べましたが、#.5 を上に丸めるために数字が見逃される可能性があるようです。

これを機能させる方法はありますか？

次のコード行があります。

コードをコンパイルすると、次のエラーが発生します。

私は#include <algorithm>ファイルの冒頭でやったのですが、エラーを理解できないようです。関数呼び出しで使用されるコンテナーは次のとおりです。

ありがとう。

バイナリ検索の場合、ファイル内のレコードを見つけるために必要な比較の平均数はいくつですか？

プロジェクトでは、バイナリ検索を実装する必要があります。このバイナリ検索では、重複が許可されます。ターゲットに一致するすべてのインデックス値を取得する必要があります。重複が途中にあることが判明した場合、私はこのようにすることを考えました:

Target = G 次の並べ替えられた配列があるとします。

G D D E D E G D D G D G D G D G G G G G G G G G G G G G G G G G G G G G G G A G G G G G G G G G G G G G G G G G G C絶対絶対G.GabたG.

両方のターゲット マッチがあり、すべてのターゲット マッチが必要なので、すべてを取得する良い方法は mid + 1 が同じ値である場合にチェックすることだと思いました。そうである場合は、そうでなくなるまで右中央に移動し続けます。したがって、次のようになります。

B, D, E, F, G, G, G, G, G, G (MID), Q, RS, S, Z

次に、0 から mid までカウントして、ターゲットの一致をカウントアップし、それらのインデックスを配列に格納して返します。

ミッドが一致し、重複が初めてミッドにあり、アレイの両側にある場合、それを行うことを考えていました。

では、最初に一致しなかった場合はどうなるでしょうか。例えば：

B, D, E, F, G, G, J, K, L, O, Q, R, S, S, Z

次に、通常どおり mid を取得し、first から mid-1 まで二分探索を呼び出します。

G D D D D D G D D D G D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D D G

G は F より大きいため、mid+1 から last まで二分探索を呼び出します。

G、G、J.

ミッドはマッチです。マッチなのでmid+1からlastまでforループで検索し、マッチ数をカウントアップしてマッチインデックスを配列に格納して返す。

これは、バイナリ検索がすべての重複を取得するための良い方法ですか? 私のアルゴリズムに問題があり、ヒントや提案があれば教えてください。私が見る唯一の問題は、すべての一致が私のターゲットである場合、基本的に配列全体を検索することになりますが、その場合でもすべての重複を取得する必要があるということです。

ありがとうございました

ところで、私のインストラクターは、ベクトル、ハッシュ、またはその他のものは使用できないと言いました。彼は、私たちが配列レベルにとどまり、それらの使用と操作に慣れることを望んでいます。

ここで質問がありましたが、保存されませんでした。完全にバランスの取れていないツリー (右側のノード 1 ～ 15) のバランスをとるのに問題があります。

スタックオーバーフローが発生して困っています。

文字列の2つの等しいリストを読み取り、最初のリストの単語のうち2番目のリストにもある単語の数を単純に出力する必要があります。私に拡張された結果を与えていません、そして私は問題がbinary_searchにあると思います。私に理由を教えてくれる ？

二分探索木の重複に関する問題を解決するにはどうすればよいですか？

任意のデータ型で構成できる汎用BSTを作成したいのですが、BSTが汎用である場合、ツリーに追加する方法がわかりません。必要なコードはすべて以下のとおりです。BSTをロケーションで構成し、x変数でソートする必要があります。どんな助けでも大歓迎です。

見てくれてありがとう。

その他のコード

二分探索を使用して配列内のn個のソートされた個別の整数すべてを見つけるために必要な比較の総数はいくつですか？数はnlog2 n （ ₂が底）だと思いますが、よくわかりません。どう思いますか？