プロジェクトでは、バイナリ検索を実装する必要があります。このバイナリ検索では、重複が許可されます。ターゲットに一致するすべてのインデックス値を取得する必要があります。重複が途中にあることが判明した場合、私はこのようにすることを考えました:
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ループで検索し、マッチ数をカウントアップしてマッチインデックスを配列に格納して返す。
これは、バイナリ検索がすべての重複を取得するための良い方法ですか? 私のアルゴリズムに問題があり、ヒントや提案があれば教えてください。私が見る唯一の問題は、すべての一致が私のターゲットである場合、基本的に配列全体を検索することになりますが、その場合でもすべての重複を取得する必要があるということです。
ありがとうございました
ところで、私のインストラクターは、ベクトル、ハッシュ、またはその他のものは使用できないと言いました。彼は、私たちが配列レベルにとどまり、それらの使用と操作に慣れることを望んでいます。