Сложность: medium
Предположим, что массив длиной 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).
Пример:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
👨💻 Алгоритм:
1⃣Нахождение середины массива:
Определите элемент, находящийся посередине массива.
2⃣Определение направления поиска:
Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины.
Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.
3⃣Остановка поиска при нахождении точки перегиба:
Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий:
nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом.
nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.
😎 Решение:
class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int left = 0, right = nums.length - 1;
if (nums[right] > nums[0]) {
return nums[0];
}
while (right >= left) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}
if (nums[mid] > nums[0]) {
left = mid + 1;
} else {
}
}
return Integer.MAX_VALUE;
}
}Ставь 👍 и забирай 📚 Базу знаний