Search in Rotated Sorted Array

---

Search in Rotated Sorted Array: 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.

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

---

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

---

Try this Problem on your own or check similar problems:

1. Search in Rotated Sorted Array II
2. Find Minimum in Rotated Sorted Array

Solution:

Java

public int search(int[] nums, int target) {
    int start = 0, end = nums.length-1;
    while(start <= end){
        int mid = start + (end - start) / 2;

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

        if(nums[mid] > target){
            if(nums[mid] >= nums[start] && nums[start] > target){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }else{
            if(nums[mid] <= nums[end] && nums[end] < target){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
    }
    return -1;
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let start = 0;
  let end = nums.length - 1;
  while (start <= end) {
    let mid = Math.floor(start + (end - start) / 2);
    if (nums[mid] === target) {
      return mid;
    }
    if (nums[mid] > target) {
      if (nums[mid] >= nums[start] && nums[start] > target) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    } else {
      if (nums[mid] <= nums[end] && nums[end] < target) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
  }
  return -1;
};

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                if nums[mid] >= nums[start] and nums[start] > target:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                if nums[mid] <= nums[end] and nums[end] < target:
                    end = mid - 1
                else:
                    start = mid + 1
        return -1

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
       int start = 0;
        int end = nums.size() - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                if (nums[mid] >= nums[start] && nums[start] > target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                if (nums[mid] <= nums[end] && nums[end] < target) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(logn)
• Space Complexity: O(1)

---

Explanation:

Modified binary search which we break down into three steps:

• First we check if the number at mid is the target and return it as the result
• If it's not we first check if the element at mid is larger than our target and we break down this case further in two subcases:

1. start..mid is sorted sequence nums[mid] >= nums[start], and if nums[start] > target that means all numbers in the left part are larger than target so we have to search in the right part start = mid + 1
2. Otherwise we know the left is rotated and we have to search in it (mid..end is sorted, but we know our target is smaller than mid and we can skip the whole right side)

• If element at mid is smaller than the target again we have two subcases:

1. mid..end is sorted sequence nums[mid] <= nums[end] and target is larger than the element at end that means it's larger than all elements on the right side so search for the element in left side end = mid - 1
2. Otherwise we know right is rotated and we have to search in that half (start..mid is sorted and we know target is larger than element at mid, so it is larger than every element on the left side and we can discard it)

If we don't find the target we return -1.