[LeetCode] 33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

Solution

Since the sorted array is rotated somehow, we should first compare whether the target is in the first half or the second half of the array.

After comparing the target with the nums[0], we can decide whether we start the for loop from the first element of the array or the last one.

The code is shown as below.

Java

public class Solution {
    public int search(int[] nums, int target) {
        
        if (nums.length == 0)
            return -1;
            
        int lo = 0, hi = nums.length;
        if(target < nums[0]){
            for(int i=nums.length-1;i>=0;i--)
                if(nums[i] == target)
                    return i;
        }
        else{
            for(int i=0;i<nums.length;i++)
                if(nums[i] == target)
                    return i;
        }
        return -1;
    }
}

Solution 2

Also, we can implement binary search.

However, since the array is not sorted, we have to fix the array before implementing binary search in normal way.

To restore the array to sorted one, we can first compare the target with the first element of the array. If the target is smaller than the first element, it means the target should be at the second half of the array.

And in order to implement binary search, we can then set every element in the first half of the array to Integer.MIN_VALUE, and in this way, the array turns into a sorted array.

Example:

For nums looks like this:

[12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

If target is let's say 14, then we adjust nums to this, where "inf" means infinity:

[12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

If target is let's say 7, then we adjust nums to this:

[-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Other than this little trick, there is nothing much to discuss. The code is shown as below.

Java

public class Solution {
    public int search(int[] nums, int target) {
        
        int lo = 0, hi = nums.length;
        
        while (lo < hi) {
        int mid = (lo + hi) / 2;
        
        double num = (nums[mid] < nums[0]) == (target < nums[0]) ? nums[mid]
                   : target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
                   
        if (num < target)
            lo = mid + 1;
        else if (num > target)
            hi = mid;
        else
            return mid;
        }
        return -1;
    }
}

However, the run time of this two method does not seem to vary dramatically.