arrays - 数値がn/2回存在するか、ソートされた配列に存在しないかを見つけるための最小の複雑さ

Question

ソートされた配列が与えられた場合、要素が n/2 回以上存在するか、o(1) に存在しないかを見つけることは可能ですか? 中央の要素が探している要素と等しくない場合、それが n/2 回未満存在するか、まったく存在しないと確実に言えます。しかし、中央の要素が探している要素と等しい場合、その出現回数が n/2 回を超えているかどうかを見つけることは可能でしょうか?

Answer 1

O(lg(n)) を見ていると思います。要素の最初と最後のインスタンスを見つけるには、バイナリ検索を実行する必要があります (要素が正確に n/2 回存在すると仮定します)。