# 33. Search in Rotated Sorted Array (Medium)

https://leetcode.com/problems/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```

## Solutions

https://www.cnblogs.com/springfor/p/3858140.html

``````class Solution {
public int search(int [] A,int target){
if(A==null||A.length==0)
return -1;

int low = 0;
int high = A.length-1;

while(low <= high){
int mid = (low + high)/2;
if(target < A[mid]){
if(A[mid]<A[high])//right side is sorted
high = mid - 1;//target must in left side
else
if(target<A[low])//target<A[mid]&&target<A[low]==>means,target cannot be in [low,mid] since this side is sorted
low = mid + 1;
else
high = mid - 1;
}else if(target > A[mid]){
if(A[low]<A[mid])//left side is sorted
low = mid + 1;//target must in right side
else
if(target>A[high])//right side is sorted. If target>A[high] means target is not in this side
high = mid - 1;
else
low = mid + 1;
}else
return mid;
}

return -1;
}
}
``````