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.
Входные данные: nums = [3,4,5,1,2]
Результат: 1
Пояснение: Исходный массив был [1,2,3,4,5] повернут 3 раза.
Пример 2.
Входные данные: nums = [4,5,6,7,0,1,2]
Результат: 0
Пояснение: Исходный массив был [0,1,2,4,5,6,7], и он был повернут 4 раза.
Пример 3.
Входные данные: nums = [11,13,15,17]
Результат: 11
Пояснение: Исходный массив был [11,13,15,17], и он был повернут 4 раза.
Решение.
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r && nums[l] > nums[r]) {
auto m = (l + r) / 2;
if (nums[l] <= nums[m]) {
// непрерывная последовательность слева
l = m + 1;
} else {
// непрерывная последовательность справа
r = m;
}
}
return nums[l];
}
};
Поиск максимума.
class Solution {
public:
int findMax(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r && nums[l] > nums[r]) {
auto m = (l + r) / 2;
if (nums[l] <= nums[m]) {
// непрерывная последовательность слева
l = m;
} else {
// непрерывная последовательность справа
r = m - 1;
}
}
return nums[r];
}
};