2

重複の可能性：
BSTでx未満のすべての数値を検索

バイナリ検索を変更して、特定の数より少ないソートされた配列内の数を見つけるにはどうすればよいですか？

4

5 に答える 5

2

すでに並べ替えられた数値の配列がある場合は、バイナリ検索アルゴリズムを使用して、並べ替えられた配列でアイテムの挿入ポイントを見つけるだけです。挿入ポイントのインデックスは、ターゲット数より少ない要素の数を示します。

あなたのコメントであなたは2つの良い質問を提起しました：

  • 番号がリストにない場合はどうなりますか？

これを処理するには、数値が存在する場合にその数値が存在するはずのポイント、つまり現在の要素がxより大きく、前の要素がxより小さいインデックスが見つかるまで検索を続けます。

  • 重複がある場合はどうなりますか？

これを処理するには、最初に要素を見つけたときに停止するのではなく、下限と上限が一致するまで検索を続けます。xに等しい値に達した場合は、高すぎる数値を見つけた場合と同じように扱い、二等分し続けます。

于 2010-06-27T20:26:52.947 に答える
2

二分探索によって返された値のインデックスよりも小さいすべての数値を返します。

于 2010-06-27T21:36:06.297 に答える
0

番号を見つけてインデックスを確認します。

于 2010-06-27T23:15:08.470 に答える
0

これは具体的には数値の配列であり、比較可能なオブジェクトだけではないため、補間検索を確認することをお勧めします。数値が均一に分布している場合、O（log n）ではなくO（log log n）時間でインデックスを見つけることができます。

于 2010-06-27T23:48:02.220 に答える
-1

指定された数よりも小さい最大数を二分探索します。あなたがその位置を取得すると、その位置はあなたが興味を持っているカウントにも直接関係します。

この擬似コードは正しい軌道に乗るはずですが、私はそれをテストしていません。k=与えられた数

while left < right
    mid = (left + right) / 2
    if arr[mid] >= k // too big, not interested
        right = mid;
    else             // maybe too small, try bigger values
        left = mid + 1

 right - 1 or left - 1 (they're equal) is the position you're after.

例：8 11 13 20 50、k = 19

left = 1, right = 5
mid = 3
arr[3] = 13 < 19 => left = 4

left = 4, right = 5
mid = 4
arr[4] = 20 >= 19 => right = 4

left >= right => left - 1 = 4 - 1 = 3 is the position you're after
于 2010-06-27T20:53:42.153 に答える