Сложность: medium
Пиковым элементом называется элемент, который строго больше своих соседей.
Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков.
Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.
Необходимо написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
👨💻 Алгоритм:
1️⃣Начальная проверка:
Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.
2️⃣Определение направления поиска:
Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.
Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.
3️⃣Завершение поиска:
Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности.
😎 Решение:
var findPeakElement = function (nums) {
return search(nums, 0, nums.length - 1);
};
var search = function (nums, l, r) {
if (l == r) return l;
let mid = Math.floor((l + r) / 2);
if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
return search(nums, mid + 1, r);
};Ставь 👍 и забирай 📚 Базу знаний