Elemento di picco in un array in c

Question

Viene fornita una matrice di numeri interi. Devo trovare un elemento di punta in esso. Un elemento dell'array è di picco se è NON più piccolo rispetto ai suoi vicini. Per gli elementi angolari, considerare solo un vicino.

Ad esempio:

Per matrice di ingresso {10, 20, 15, 2, 23, 90, 67} ci sono due elementi di picco: 20 e 90. devo restituire qualsiasi elemento un picco.

La soluzione che ho provato è una scansione lineare di array e ho trovato un elemento di picco. La complessità temporale del caso peggiore di questo metodo sarebbe O (n).

È possibile trovare l'elemento di picco nella peggiore complessità temporale migliore di O (n)?

Answer 1

Sì, è possibile farlo in O (log n) utilizzando un'idea simile alla ricerca binaria. Punta al centro del vettore e controlla i suoi vicini. Se è maggiore di sia dei suoi vicini, quindi restituire l'elemento, è un picco. Se l'elemento giusto è maggiore, trova il picco ricorsivamente nella parte destra dell'array. Se l'elemento di sinistra è maggiore, trova il picco ricorsivamente sul lato sinistro dell'array.

Answer 2

Sì, è possibile trovarlo in una migliore complessità temporale. Utilizzo del metodo di deviazione e conquista

Il seguente collegamento ti aiuterà. http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

Answer 3

Come per di altre risposte popoli (di seguito il mio) del codice (con 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; 
} 

usato questo per il corso del MIT 6.006 OCW può essere verificare che fuori pure

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