arrays - 要素 'x' が Ω(log(n)) 実行時にソートされた配列にあるかどうかを判断する方法は?

Question

要素が実行時xにソートされた配列Aにあるかどうかを判断するにはどうすればよいですか?Ω(log(n))

私の最初の答え: 二分探索を使用し、その高さが少なくとも log_3(n) であることを示す決定木を作成します。したがって、高さのある三分木にhは3^h葉があり、log_3(n) ∈ Ω(log(n)) です。

Answer 1

The decision tree is a good instinct. Now imagine not actually creating the tree, but performing the same search through it anyway....