cの配列のピーク要素

Question

整数の配列が与えられています。私はそれにピーク要素を見つける必要があります。 配列要素は、より小さくない場合、その近傍よりです。 コーナー要素については、1つのネイバーだけを考慮してください。例えば

：20と90、私はいずれかのピーク要素を返す必要が：

入力アレイ{10, 20, 15, 2, 23, 90, 67} ための二つのピークの要素があります。

私が試した解決策は、アレイの線形スキャンであり、ピークの要素が見つかりました。この方法の最悪の場合の時間複雑さはO（n）である。

最悪の時間の複雑さでピーク要素がO（n）よりも優れていますか？

Answer 1

はい、バイナリ検索に似た考え方でO（log n）で実行できます。ベクトルの中央を指して、その近傍をチェックします。それがよりも大きい場合は、隣人のの両方を返し、要素を返します。ピークです。右の要素が大きい場合は、配列の右側で再帰的にピークを見つけます。左の要素が大きい場合は、配列の左側で再帰的にピークを見つけます。

Answer 2

はい、時間の複雑さが増しています。除外と征服の方法を使用する

次のリンクはあなたを助けます。 （鉱山以下）の他の人々の答え（Oと（nはログ））いくつかのコードを1として http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

Answer 3

：

// A divide and conquer solution to find a peak element element 
#include <stdio.h> 

// A binary search based function that returns index of a peak element 
int findPeakUtil(int arr[], int low, int high, int n) 
{ 
    // Fin index of middle element 
    int mid = low + (high - low)/2; /* (low + high)/2 */ 

    // Compare middle element with its neighbours (if neighbours exist) 
    if ((mid == 0 || arr[mid-1] <= arr[mid]) && 
      (mid == n-1 || arr[mid+1] <= arr[mid])) 
     return mid; 

    // If middle element is not peak and its left neighbor is greater than it 
    // then left half must have a peak element 
    else if (mid > 0 && arr[mid-1] > arr[mid]) 
     return findPeakUtil(arr, low, (mid -1), n); 

    // If middle element is not peak and its right neighbor is greater than it 
    // then right half must have a peak element 
    else return findPeakUtil(arr, (mid + 1), high, n); 
} 

// A wrapper over recursive function findPeakUtil() 
int findPeak(int arr[], int n) 
{ 
    return findPeakUtil(arr, 0, n-1, n); 
} 

/* Driver program to check above functions */ 
int main() 
{ 
    int arr[] = {1, 3, 20, 4, 1, 0}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    printf("Index of a peak point is %d", findPeak(arr, n)); 
    return 0; 
} 

MIT 6.006 OCWのコースのためにこれを使用し、同様のことをチェックアウトすることができる

http://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf