c - c の配列のピーク要素

Question

整数の配列が与えられます。その中でピーク要素を見つけなければなりません。隣接要素よりも小さくない場合、配列要素はピークです。コーナー要素の場合、1 つの隣接要素のみを考慮してください。

例えば：

入力配列{10, 20, 15, 2, 23, 90, 67} には、20 と 90 の 2 つのピーク要素があります。いずれか 1 つのピーク要素を返す必要があります。

私が試した解決策は、配列の線形スキャンであり、ピーク要素が見つかりました。この方法の最悪の場合の時間計算量は O(n) になります。

O(n) よりも優れた最悪の時間複雑度でピーク要素を見つけることができますか?

Answer 1

はい、バイナリ検索に似たアイデアを使用して、O(log n) で実行できます。ベクトルの中央をポイントし、その近傍を確認します。隣接要素の両方よりも大きい場合は、要素を返します。これはピークです。右側の要素の方が大きい場合は、配列の右側で再帰的にピークを見つけます。左の要素が大きい場合は、配列の左側で再帰的にピークを見つけます。