algorithm - アルゴリズムの設計と分析

Question

私は問題に行き詰まっています。問題を解決する必要があります。ここにあります:

そのようなインデックスが見つからない場合に を返すようiに、配列内のインデックスを見つけるアルゴリズムを記述します。A[i] = i0<=i<=n-1-1

私はこの質問をO(n)時間内に行いましたが、私の仲間は、それよりも短い時間で行うことができると言っています。O(lg(n))

より良い解決策を見つけるのを手伝ってくれる人はいますか?? もしそうなら、親切にこの投稿に返信してください..ありがとう

Answer 1

配列がソートされている場合は、バイナリ検索O(lg(n))を使用して検索できます。それ以外の場合は必要になります。O(n)

Answer 2

配列がソートされていない場合、これは不可能です。決定論的で非確率的なアルゴリズムを探していると思います。配列の O(log(n)) セルにアクセスすることで問題を解決するアルゴリズム「Alg」が存在すると仮定します。V(I) を、与えられた入力 I で Alg がアクセスしたセルのセットとします。また、入力 I1 に対する答えが -1 で、Alg が -1 を正しく返すと仮定します。ここで、V(I1) にない I1 のセルの 1 つを変更し、Alg に再度渡します。確かに、Alg は再び -1 を返しますが、これは正解ではありません。

Answer 3

配列でバイナリ検索を行うことになっています。問題文の非常に重要な部分を見逃しています - 配列は事前にソートされている必要があります。