153. Find Minimum in Rotated Sorted Array

Задача

Предположим, что массив длины n , отсортированный в порядке возрастания, повернут (сдвинут) от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:

• [4,5,6,7,0,1,2], если он был повернут 4 раза.
• [0,1,2,4,5,6,7], если он был повернут 7 раз.

Заметьте, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]] .

Вам дан отсортированный повернутый массив nums из уникальных элементов, верните минимальный элемент этого массива.

Вы должны написать алгоритм, который работает за время O(log n) .

Примеры

Пример 1

Input: nums = [3,4,5,1,2]
Output: 1

Пояснение

Исходный массив [1,2,3,4,5] был сдвинут 3 раза.

Пример 2

Input: nums = [4,5,6,7,0,1,2]
Output: 0

Пояснение

Исходный массив [0,1,2,4,5,6,7] был сдвинут 4 раза.

Пример 3

Input: nums = [11,13,15,17]
Output: 11

Пояснение

Исходный массив [11,13,15,17] был сдвинут 4 раза.

Решение

Решение

/**
 * Временная сложность: O(log N)
 * Поскольку на каждой итерации мы делим область поиска пополам.
 *
 * Пространственная сложность: O(1)
 * Используем только несколько переменных для указателей, дополнительная память не зависит от размера массива.
 */
var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1;
 
    while (left < right) {
        // Вычисляем середину
        const mid = left + Math.floor((right - left) / 2);
 
        // Сравниваем середину с ТЕКУЩИМ правым краем
        if (nums[mid] > nums[right]) {
            // Если середина больше правого края, значит мы на "высоком" уступе.
            // Минимальный элемент точно правее (и mid им быть не может).
            left = mid + 1;
        } else {
            // Если середина меньше или равна правому краю, мы на "низком" уступе (или массив не повернут).
            // Минимальный элемент может быть здесь (mid) или левее.
            // Поэтому не отбрасываем mid (не делаем -1).
            right = mid;
        }
    }
 
    // В конце left и right сойдутся на минимальном элементе
    return nums[left];
};