Пиковый элемент в массиве в c

Мне задан массив целых чисел. Я должен найти в нем пиковый элемент. Элемент массива является максимальным, если он НЕ меньше, чем его соседи. Для угловых элементов рассмотрим только одного соседа.

Например:

Для входного массива {10, 20, 15, 2, 23, 90, 67} есть два пиковых элемента: 20 и 90. Мне нужно вернуть любой один пиковый элемент.

Решение, которое я попробовал, представляет собой линейное сканирование массива, и я нашел пиковый элемент. Худшей временной сложностью этого метода будет O (n).

Можно ли найти пиковый элемент в наихудшей временной сложности лучше, чем O (n)?

Ответ 1

Да, вы можете сделать это в O (log n), используя идею, похожую на двоичный поиск. Направьте середину вектора и проверьте его соседей. Если он больше и его соседей, то верните элемент, это пик. Если правый элемент больше, то найдите пик рекурсивно в правой части массива. Если левый элемент больше, то найдите пик рекурсивно в левой части массива.

Ответ 2

Да, это можно найти в более сложной временной сложности. Использование метода девайса и завоевания

Следующая ссылка вам поможет. http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

Ответ 3

В соответствии с другими ответами людей (ниже моего) некоторый код (с 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;
}

Используется для курса MIT 6.006 OCW, возможно, также проверьте это.

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