# 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;

}
};
``````