Есть массив специального вида — его можно поделить на две части так, что одна будет возрастающей, а другая убывающей.
Надо найти «пик», формально, такой индекс i что верно: A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
Вопросы, которые можно задать:
Очевидное решение — пройтись по массиву и найти первый индекс где прекращается восходящий тренд. В худшем случае придётся пройти почти весь массив. Сложность O(N).
Есть ли решение лучше?
Мы понимаем, что есть два тренда: восходящий и нисходящий, и есть ровно один пик, который лежит на стыке. Можно взять любые две соседние точки и задать себе вопрос — какой это тренд? Если восходящий, значит пик где-то справа, если нисходящий — значит слева.
Смогли распознать алгоритм? Верно, это ж бинарный поиск!
/**
* @param {number[]} A
* @return {number}
*/
var peakIndexInMountainArray = function(A) {
// границы в пределах которых будем искать ответ
let start = 0;
let end = A.length - 1;
// бинарный поиск двигает start и end друг к другу,
// сужая количество возможных вариантов для поиска вдвое на каждом шаге
while (start < end) {
const middle = Math.floor((start + end) / 2);
// т.к. минимальная длина 3 → выход за границу массива не страшен,
// но в общем случае здесь нужно быть аккуратнее (проверять edge cases!)
// Если длина массива 1, то middle будет равен 0,
// соответственно A[middle + 1] — за границей массива
if (A[middle] < A[middle + 1]) {
// middle оказался в восходящем тренде,
// соответственно надо продолжать поиск справа,
// при этом раз middle + 1 оказался больше — значит он ближе к пику
start = middle + 1;
} else {
// middle оказался в восходящем тренде,
// соответственно надо продолжать поиск слева,
// при этом раз middle оказался больше — значит он ближе к пику
end = middle;
}
}
// на данном этапе A[start] > A[end] и отличаются на единицу,
// т.е. мы нашли самое начало нисходящего тренда — это и есть пик
return start;
};
Сложность O(log N) т.к. мы уменьшали количество возможных вариантов вдвое на каждом шаге, то в худшем случае нужно сделать log N итераций цикла.
✈️ Телеграм-канал — https://t.me/coding_interviews