33. Search in Rotated Sorted Array& 81. Search in Rotated Sorted Array II

Published on July 4, 2023

Question1

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

Algorithm1

There are three ways to solve the problem. Let's discuss one by one in the next section.

Code1

Code1 Find the sorted side

Wrong Code

In this code I tried to compare the target and the num[mid], however, the core is to identify if the range is sorted, so target here doesn't matter. Comparing target and either left or right solely won't determine the direction.

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                if (target >= nums[left]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[right-1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return -1;
    }
}

Right code

We need to find mark sure it's the sorted range, so after we check the left and right of the range, then we also need to compare the target with leftmost element and rightmost element of selected range, to determine our next query range.

By doing this, we are willingly or positively looking for the sorted range and search the target.

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else {
                if (nums[left] < nums[mid]) {
                    if (nums[left] <= target && target <= nums[mid]) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                } else {
                   if (nums[mid] <= target && target <= nums[right - 1]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
            }
        }
        return -1;
    }
}

Code2 Find the pivot the search separately

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        int mid = left + (right - left) / 2;
        // find the pivot
        while (left < right) {
            if (nums[mid] > nums[nums.length - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
            mid = left + (right - left) / 2;
        }
        
        int res = binarySearch(nums, left, nums.length, target);
        if (res != -1) {
            return res;
        }
        return binarySearch(nums, 0, right, target);
        
    }
    
    private int binarySearch(int[] nums, int left, int right, int target) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

Code3 Find the pivot and make a shift

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        int mid = left + (right - left) / 2;
        // find the pivot
        while (left < right) {
            if (nums[mid] > nums[nums.length - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
            mid = left + (right - left) / 2;
        }
        
        int n = nums.length;
        int pivot = left;
        int shift = n - pivot;
        left = (pivot + shift) % n;
        right = (pivot - 1 + shift) % n;

        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[(mid - shift + n) % n] == target) {
                return (mid - shift + n) % n;
            } else if (nums[(mid - shift + n) % n] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;   
    }
}

Question2

The following up question Question 81, where there are duplicate elements. If you cannot see the different and adopt the previous solution, you will be not able to handle the situation like: target 2, nums = [1,2,1,1,1].

In such case, nums[left] = 1, nums[mid] = 1, and nums[right] = 1. You cannot distinguish the sorted range only by comparing them. Since we know we have duplicate elements, we could just skip them to eliminate the affect of the duplicated elements. Why we can skip them? Because we are looking for existence and only if they are in the range and in the sorted range, it's ok. For example: for array [1, 2, 1,1,1], when we are searching, we found nums[left] = nums[mid] = 1, so we simply move the left forward step. Same as the right bound.

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[left] == nums[mid]) {
                left++;
            } else if (nums[right] == nums[mid]) {
                right--;
            } else if (nums[left] < nums[mid]) {
                if (nums[left] <= target && target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] <= target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}