在翻转的有序数组中搜索

Problem

There is an integer array nums sorted in ascending order with distinct values. Before being passed to your function, nums may be left rotated at an unknown index k.

For example: [0,1,2,4,5,6,7] might be rotated by 3 positions and become: [4,5,6,7,0,1,2]

Given the rotated array nums and an integer target, return the index of target if it exists in nums. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

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

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

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

Idea

Use binary search. At each step, look at the middle element. Because the array is rotated, one of the two halves must still be normally sorted.

If the left half is sorted: - Check whether the target lies between nums[left] and nums[mid]. - If yes, search the left half. - Otherwise, search the right half.

If the right half is sorted: - Check whether the target lies between nums[mid] and nums[right]. - If yes, search the right half. - Otherwise, search the left half. Continue until the target is found or the search range becomes empty.

Time complexity: O(log n), Space complexity: O(1)

Pseudo-code

left = 0;
right = length(nums) - 1;

while (left <= right) {
    mid = left + (right - left) / 2;

    if (nums[mid] == target) {
        return mid;
    }

    if (nums[left] <= nums[mid]) {
        // left half is sorted

        if (nums[left] <= target && target < nums[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    else {
        // right half is sorted

        if (nums[mid] < target && target <= nums[right]) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
}

return -1;