5

二分探索に関する Jon Bentley の章を含む複数の記事を読みました。これは、正しいバイナリ検索ロジックについて私が理解していることであり、私が行った簡単なテストで機能します。

binarysearch (arr, low, high, k)
    1. while (low < high)
        2. mid  = low + (high - low)/2
        3. if (arr[mid] == k)
               return mid
        4. if (arr[mid] < k )
               high = mid -1
        5. else 
               low = mid + 1

ソートされた重複で最初の出現を見つけるには、ミッドを返すのではなく、条件が続行する場合に 3 行目をチャンスとします。

binarysearch_get_first_occur_with_duplicates (arr, low, high, k)
    1. while (low < high)
        2. mid  = low + (high - low)/2
        3. if (arr[mid] == k)
               high = mid - 1
               low_so_far = arr[mid]
        4. if (arr[mid] < k )
               high = mid -1
        5. else 
               low = mid + 1
        return low_so_far

同様に、繰り返される要素の最高のインデックスを取得するには、次の場合に実行しlow = mid + 1て続行しますarr[mid]==k

このロジックは機能しているようですが、複数の場所でループ不変式が次のように表示されます

while (low + 1 < high)

low + 1 < high混乱しており、の代わりにいつ使用したいのかを理解したいと思っていますlow < high。

上記で説明したロジックではlow + 1 < high、単純な例でテストすると、状態がエラーになります。

low + 1 < highの代わりにwhileループで使用する理由とタイミングを誰かが明確にすることはできますかlow < high?

4

1 に答える 1

3

不変条件がターゲットが にある必要がある場合は、 ;low <= i <= highを使用します。while (low < high)不変条件がターゲットが存在する必要がある場合はlow <= i < high、 を使用しますwhile (low + 1 < high)。[これを確認してくれた David Eisenstat に感謝します。]

于 2013-08-12T22:46:40.690 に答える