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, если его нет. Вы должны максимально сократить общее количество шагов операции.

Примеры

Пример 1

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Пример 2

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Решение

Решение

/**
 * Временная сложность:
 * - В среднем: O(log N) (как обычный бинарный поиск).
 * - В худшем случае: O(N) (когда много дубликатов, например [1,1,1,1], алгоритм вырождается в линейный проход).
 * 
 * Пространственная сложность: O(1) (только указатели).
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
 
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
 
        if (nums[mid] === target) return true;
 
        // Обработка дубликатов: если границы и центр равны, 
        // мы не можем определить отсортированную часть -> сужаем окно вручную.
        if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
            left++;
            right--;
            continue;
        }
 
        // Левая половина отсортирована?
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // Ищем слева
            } else {
                left = mid + 1; // Ищем справа
            }
        }
        // Правая половина отсортирована?
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // Ищем справа
            } else {
                right = mid - 1; // Ищем слева
            }
        }
    }
 
    return false;
};