81. Поиск в сдвинутом отсортированном массиве (Search in Rotated Sorted Array II)
Задание.
Существует целочисленный массив nums, отсортированный в порядке неубывания (не обязательно с различными значениями).
Перед передачей вашей функции nums поворачивается с неизвестным индексом поворота k (0 <= k < nums.length) так, чтобы результирующий массив [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] был (0-индексированный).
Например, [0,1,2,4,4,4,5,6,6,7] может быть повернуто с индексом поворота 5 и стать [4,5,6,6,7,0,1,2,4,4].
Даётся массива nums после поворота и целочисленное target.
Верните true, если target находится в nums, или false, если target нет в nums.
Нужно максимально сократить общие этапы операции.
Пример 1.
Входные данные: nums = [2,5,6,0,0,1,2], target = 0
Результат: true
Пример 2.
Входные данные: nums = [2,5,6,0,0,1,2], target = 3
Результат: false
Решение.
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if (nums[mid] == target || nums[l] == target || nums[r] == target)
return true;
// если на краях дубли совпадают с серединой, уменьшаем границы
if((nums[l] == nums[mid]) && (nums[r] == nums[mid]))
{
l++;
r--;
} else if(nums[l] <= nums[mid]) {
// непрерывная последовательность слева
if((nums[l] <= target) && (nums[mid] > target))
r = mid - 1;
else
l = mid + 1;
} else {
// непрерывная последовательность справа
if((nums[mid] < target) && (nums[r]>= target))
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
};