33. Search in Rotated Sorted Array

Задача

Имеется массив целых чисел nums, отсортированный в порядке возрастания (с уникальными значениями).

Перед передачей в вашу функцию nums, возможно, был циклически сдвинут влево на неизвестный индекс k (1 <= k < nums.length), так что результирующий массив стал [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (индексация с 0). Например, [0,1,2,4,5,6,7] мог быть сдвинут влево на 3 индекса и стать [4,5,6,7,0,1,2].

Дан массив nums после возможного сдвига и целое число target. Верните индекс target, если он есть в nums, или -1, если его нет. Алгоритм должен работать за O(log n).

Примеры

Пример 1

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

Пример 2

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

Пример 3

Input: nums = [1], target = 0
Output: -1

Решение

Решение

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