aboutsummaryrefslogtreecommitdiff
path: root/find_peak_element.c
blob: 9803f70eb70a6e8a1bd9d20cb88f49fdbcb8ada2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 162. Find Peak Element
#include "leetcode.h"

/*
 * a peak element is an element that is strictly greater than its neighbours.
 * given a 0 indexed array 'nums', find a peak element and return its index. if
 * the array contains multiple peaks, return the index to any of the peaks. you
 * may imagine that 'nums[-1] = nums[n] = -inf' in other words, an element is
 * always considered to be strictly greater than a neighbour that is outside the
 * array. you must write an algorithm that runs in 'O(log n)' time.
 */

int findPeakElement(int *nums, int numsSize) {
  if (numsSize == 1)
    return 0;
  if (numsSize == 2)
    return nums[0] > nums[1] ? 0 : 1;
  int left = 0, right = numsSize - 1, mid;
  while (left < right) {
    mid = (left + right) / 2;
    if (!mid)
      break;
    if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])
      return mid;
    else if (nums[mid] > nums[mid - 1])
      left = mid + 1;
    else
      right = mid - 1;
  }
  if (right < numsSize - 1 && right) {
    if (nums[right] > nums[right + 1] && nums[right] > nums[right - 1])
      return right;
  } else if (left < numsSize - 1 && left) {
    if (nums[left] > nums[left + 1] && nums[left] > nums[left - 1])
      return left;
  } else
    return !left ? left : right;
  return 0;
}

int main() {
  int n1[] = {1, 2, 3, 1}, n2[] = {1, 2, 1, 3, 5, 6, 4};
  printf("%d\n", findPeakElement(n1, ARRAY_SIZE(n1))); // expect: 2
  printf("%d\n", findPeakElement(n2, ARRAY_SIZE(n2))); // expect: 5
}