Problem

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Follow up: what if duplicates are allowed?

NOTE : Think about the case when there are duplicates. Does your current solution work? How does the time complexity change?*

Write a function to determine if a given target is in the array.

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

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.

Method 1 - 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;
	}
}

Complexity

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

Method 2 - 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;
    }
}

Complexity

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