Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

👨‍💻 Алгоритм:

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

class Solution {
    function findInMountainArray($target, $mountainArr) {
        $length = $mountainArr->length()

        $low = 1
        $high = $length - 2
        while ($low != $high) {
            $mid = (int)(($low + $high) / 2)
            if ($mountainArr->get($mid) < $mountainArr->get($mid + 1)) {
                $low = $mid + 1
            } else {
                $high = $mid
            }
        }
        $peak = $low

        $low = 0
        $high = $peak
        while ($low < $high) {
            $mid = (int)(($low + $high) / 2)
            if ($mountainArr->get($mid) < $target) {
                $low = $mid + 1
            } else {
                $high = $mid
            }
        }
        if ($mountainArr->get($low) == $target) {
            return $low
        }

        $low = $peak + 1
        $high = $length - 1
        while ($low < $high) {
            $mid = (int)(($low + $high) / 2)
            if ($mountainArr->get($mid) > $target) {
                $low = $mid + 1
            } else {
                $high = $mid
            }
        }
        if ($mountainArr->get($low) == $target) {
            return $low
        }

        return -1
    }
}

Ставь 👍 и забирай 📚 Базу знаний