Задача с собеседования в Facebook(Meta): Найти пиковый элемент
#собеседование #interview #algo #meta #binarysearch

Публикую решение вчерашней задачи с собеседования в Facebook.

Дан массив целый чисел. Любые два соседних числа не равны друг другу. Найти любой пик в массиве. Пик это элемент в массиве, который больше своих соседей слева и справа. Т.е. arr[i-1] < arr[i] > arr[i + 1] в этом случае i-индекс пика в массиве. Можно предположить, что arr[-1] = arr[n] = минус бесконечность.

Решение:
1. Первое решение, которое приходит в голову - линейный поиск. Просто в цикле пройти по массиву и сравнить каждый элемент с соседями. Как только найдем arr[i-1] < arr[i] > arr[i + 1] вернуть i. Временная сложность такого решения: O(n).
Можно еще немного упростить:
проверять только arr[i] > arr[i + 1],
т.к. дано, что на краях значения это минус бесконечность, значит вначале массив возрастает, можно найти первый случай, когда массив убывает.
Код:

public int findPeakElement(int[] nums) {
  for (int i = 0; i < nums.length -1; i++) {
    if (nums[i] > nums[i + 1]) return i;
  }
  return nums.length - 1;
}

2. Можно ли еще улучшить решение? Т.к. дано, что соседние элементы не равны друг другу - в массиве присутствуют отрезки, где массив только возрастает или только убывает. Можно это использовать для применения бинарного поиска.
Т.к. нам нужно найти любой пик, то вполне можно начать поиск с середины массива, как в бинарном поиске.
Давайте попробуем применить бинарный поиск для поиска такого пика.
Пусть мы смотрим на середину массива. К каким выводам мы можем прийти смотря на серединный и соседний элемент?
Равными они не могут быть по условию.
Если следующий элемент больше середины, то массив возрастает. Значит пик точно есть справа. Иначе - слева. На следующей итерации мы снова будет смотреть на новую середину, мы не обязательно найдем вершину, возрастание к которой мы обнаружили на предыдущем шаге. Но мы точно знаем, что в новой уменьшенной области он точно есть. Рано или поздно наша область поиска будет уменьшена до одного элемента, который гарантировано будет пиком. Он будет работать за O(log(n)), что быстрее линейного поиска.
Код:

public int findPeakElement(int[] nums) {
  int left = 0;
  int right = nums.length - 1;
  while (left < right) {
    int mid = (left + right) / 2;
    if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}