Peak-Element in einem Array in c

Question

Ich habe eine Reihe von ganzen Zahlen gegeben. Ich muss ein Peak-Element darin finden. Ein Array-Element ist Spitze, wenn es nicht kleiner als seine Nachbarn ist. Für Eckelemente sollten Sie nur einen Nachbarn berücksichtigen.

Zum Beispiel:

Für Eingangsarray {10, 20, 15, 2, 23, 90, 67} gibt es zwei Spitzenelemente: 20 und 90. I jedes eine Peak Element zurückkommen müssen.

Die Lösung, die ich versuchte, ist ein linearer Scan von Array und ich fand ein Peak-Element. Die ungünstigste Zeitkomplexität dieses Verfahrens wäre O (n).

Können wir das Peakelement in der Komplexität der schlechtesten Zeit besser finden als O (n)?

Answer 1

Ja, Sie können es in O (log n) mit einer Idee ähnlich der binären Suche tun. Zeigen Sie auf die Mitte des Vektors und überprüfen Sie seine Nachbarn. Wenn es größer ist als beide seiner Nachbarn, dann geben Sie das Element zurück, es ist ein Peak. Wenn das rechte Element größer ist, suchen Sie den Peak rekursiv auf der rechten Seite des Arrays. Wenn das linke Element größer ist, suchen Sie den Peak rekursiv auf der linken Seite des Arrays.

Answer 2

Ja, es ist möglich, es in einer besseren Zeit Komplexität zu finden. Mit Devide and Conquer Methode

folgenden Link wird Ihnen helfen. http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

Answer 3

Wie schon aus anderen Völkern Antworten (unter mir) ein Code (mit O (log n)):

// 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; 
} 

verwendet, um dieses für MIT 6,006 OCW natürlich sein, dass auch Besuche

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