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.

Your algorithm's runtime complexity must be in the order of O(log n).

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

Thoguths:

1. Binary search, find the continuous parts by comparing nums[i] with nums[mid],
2. Doing binary search inside: if it does not work, return -1

Code:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i = 0;
        int j = nums.size()-1;
        while(i <= j){
            int mid = i + (j - i >> 1);
            if (nums[mid] == target) return mid;

            if(nums[i] < nums[mid]){
                if(nums[i] <= target and nums[mid] > target){
                    j = mid - 1;
                }
                else{
                    i = mid + 1;
                }
            }

            else if (nums[i] > nums[mid]){
                if (nums[mid] < target and nums[j] >= target){
                    i = mid + 1;
                }
                else{
                    j = mid - 1;
                }
            }
            else {
                i= mid + 1; //nums[i] = nums[mid]
            }
        } 

        return -1; 
    }
};

Code: Java

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

private int binarySearch(int[] nums, int left, int right, int target){
    if(left > right) return -1;
    int mid = (left + right)/2;
    if(target == nums[mid]) return mid;
    if(target > nums[mid]) {
        if(nums[mid] < nums[left] && target > nums[right]){
            return binarySearch(nums,left,mid-1,target);
        }else {
            return binarySearch(nums,mid+1,right,target);
        }
    }else{
        if(nums[mid] > nums[right] && target < nums[left]){
            return binarySearch(nums,mid+1,right,target);
        }else {
            return binarySearch(nums,left,mid-1,target);
        }
    }
}

Code: C++

class Solution {
public:
    int search(vector<int>& A, int ele) {

        int l = 0, h = A.size()-1;
        if(!A.size())
            return -1;

        while(l<h) {

            int mid = (l+h)/2;
            if(A[l] <= A[mid]) {
                if(ele >= A[l] && ele <= A[mid]) 
                    h = mid;
                else 
                    l = mid+1;
            }

            else {

                if(ele>= A[mid] && ele<=A[h])
                    l = mid;
                else
                    h = mid-1;
            }
        }
        return A[l]==ele?l:-1;

    }
};