Problem statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with $O(log n)$ runtime complexity.
Link to problem

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

Solutions

Very similar to what we did previously using Binary search, except the twist here is that upon checking the left/right subarray, the target is not guaranteed to be in the left/right subarray, it could be in the opposite subarray due to the nature of rotated array.

That is, just because the left subarray condition is satisfied does not mean that the target is guaranteed to be in the left subarray. Note that the condition is only for comparing mid and left, not mid, left and target.

The code can be a lot more compact but I kept it elaborate for proper understanding.

Pseudocode

loop until left pointer is <= right pointer
    mid = (right + left) / 2
    if numbers[mid] == target
        return mid
    if number[mid] >= number[left]
        check if target between left and mid
        assign mid to left/right accordingly
    else
        check if target between mid and high
        assign mid to left/right accordingly

Implementation in Rust

fn search(numbers: Vec<i32>, target: i32) -> i32 {
    let mut left_ptr = 0;
    let mut right_ptr = numbers.len() - 1;

    while left_ptr <= right_ptr {
        let mid_ptr = (right_ptr + left_ptr) / 2;

        if numbers[mid_ptr] == target {
            return mid_ptr as i32;
        }

        if numbers[mid_ptr] >= numbers[left_ptr] {
            // Check if target between low and mid
            if numbers[left_ptr] <= target && target <= numbers[mid_ptr] {
                right_ptr = mid_ptr;
            } else {
                left_ptr = mid_ptr + 1;
            }
        } else {
            // Check if target between mid and high
            if numbers[mid_ptr] <= target && target <= numbers[right_ptr] {
                left_ptr = mid_ptr + 1;
            } else {
                right_ptr = mid_ptr;
            }
        }
    }
    -1
}

Time Complexity: $O(log n)$
Runtime on LeetCode: $3$ms