3

これは、Steven Skiena の「アルゴリズム設計マニュアル」第 2 版、p 143 の宿題です。

からwhere{A1,A2,...An}に引き出された、ソートされた別個の整数のシーケンスが与えられたとします。に存在しない整数を見つけるアルゴリズムを与えてください。完全なクレジットを得るには、そのような最小の整数を見つけます。1mn < mO(lgN)<= mA

ソートされたシーケンスであり、O(lgN)どちらも二分探索アルゴリズムを示唆しています。私が考えることができる唯一の方法は、 から までの数字を実行し1、m各数字について二分探索を行って、順番に存在するかどうかを確認することAです。しかし、それはO(mlgN)そうではありませんO(lgN)。

4

1 に答える 1

5

A[k]次の場合にのみ、欠落よりも小さい整数があります。

A[k] > k

(1 ベースのインデックスを使用)。

したがって、欠落している最小の数を見つけるには、二分探索を行います。中央のインデックスから始めますm。の場合A[m] > m、欠落よりも小さい数がある場合はA[m]、左半分を検索します。それ以外の場合は、欠落A[m] == mよりも小さい数はなくm、右半分を検索します。

于 2012-12-10T01:32:24.950 に答える