Problem

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.

Examples

Example 1:

Input: nums = [8, 11, 13, 15, 1, 4, 6], target = 1
Output: 4

Example 2:

Input: nums = [1, 4, 6, 8, 11, 13, 15], target = 3
Output: -1

Follow up

Search in Rotated Sorted Array - Duplicates Allowed

Similar Problems

Find Minimum in Rotated Sorted Array Find Minimum in Rotated Sorted Array 2 - Duplicates allowed

Solution

We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Linear Search

The naive approach will be:

  • Iterate through the entire array, nums.
  • Compare each element in the array with target.
  • Return the index when a match is found.
  • If the iteration ends without finding the target, return -1.

Complexity

  • ⏰ Time complexity: O(n), as it checks every element one by one.
  • 🧺 Space complexity: O(1)

Method 2 - Recursive Binary Search

Algorithm

  1. Find the middle mid of array
  2. Ascertain the sorted segment of the array by comparing nums[mid] and nums[start].
    1. If nums[mid]  >  nums[start] - That means this first part of array is sorted and is without rotation. So, we choose array to search as [start] to nums[mid]
    2. Otherwise we choose nums[nums] to nums[end].
  3. Now, depending on the array we searched in step 2, we will get the sorted array now. Now if key target lies in range of the array, we will search for the element in that range, otherwise other range.

So, second step helps us get the sorted array on which we can apply binary search.

Code

Java
class Solution {

	public int search(int[] nums, int target) {
		return rotatedSearch(nums, target, 0, nums.length - 1);
	}

	private int rotatedSearch(int[] nums, int target, int left, int right) {
		if (left > right) {
			return -1;
		}

		int mid = left + (right - left) / 2;

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

		// If left sub-array is sorted
		if (nums[left] <= nums[mid]) {
			// If target is less than middle - then target may lie in this part of array
			if (nums[left] <= target && target  <= nums[mid]) {
				return rotatedSearch(nums, target, left, mid - 1);
			} else {
				return rotatedSearch(nums, target, mid + 1, right);
			}
		}

		// If right sub-array is sorted
		if (nums[mid] <= nums[right]) {
			if (nums[mid] <= target && target  <= nums[right]) {
				return rotatedSearch(nums, target, mid + 1, right);
			} else {
				return rotatedSearch(nums, target, left, mid - 1);
			}
		}

		return -1;
	}
}
Python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return self.rotated_search(nums, target, 0, len(nums) - 1)

    def rotated_search(self, nums: List[int], target: int, left: int, right: int) -> int:
        if left > right:
            return -1

        mid: int = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # If left sub-array is sorted
        if nums[left] <= nums[mid]:
            # If target lies within the sorted left sub-array
            if nums[left] <= target <= nums[mid]:
                return self.rotated_search(nums, target, left, mid - 1)
            else:
                return self.rotated_search(nums, target, mid + 1, right)

        # If right sub-array is sorted
        if nums[mid] <= nums[right]:
            # If target lies within the sorted right sub-array
            if nums[mid] <= target <= nums[right]:
                return self.rotated_search(nums, target, mid + 1, right)
            else:
                return self.rotated_search(nums, target, left, mid - 1)

        return -1

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Method 3 - Iterative Binary Search 🏆

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            }

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

        return -1;
    }
}
Python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left: int = 0
        right: int = len(nums) - 1
        
        while left <= right:
            mid: int = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            
            if nums[left] <= nums[mid]:  # left array is sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # right array is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)