# [leetcode] Search in Rotated Sorted Array

### Search in Rotated Sorted Array

Suppose a sorted array 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.

tag:binary search

10/9/2015 update

update by

l = mid + 1

r = mid

```class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
if(nums.size() == 0) return -1;
while(r > l){
int mid = l + (r - l) / 2;
if(nums[l] < nums[r]){
//not rotated, ordinary binary search
if(target > nums[mid]){
l = mid + 1;
}
else{
r = mid;
}
continue;
}
if(nums[mid] > nums[r]){
//[mid, r] is rotated
if(target > nums[mid] || target <= nums[r]){
l = mid + 1;
}
else{
r = mid;
}
}
else{
if(target >= nums[l] || target <= nums[mid]){
r = mid;
}
else{
l = mid + 1;
}
}
}
if(nums[l] == target) return l;
else return -1;
}
};```

```class Solution {
public:
int search(int A[], int n, int target) {
int i = 0;
int j = n;
while(i < j){
int mid = (i + j) / 2;
int thisV = A[mid];
if(thisV == target){
return mid;
}
if(j - i == 1){
}
if(A[i] < A[j - 1]){//no pivot, normal binary search
if(A[mid] < target){
i = mid + 1;
}
else{
j = mid;
}
}
else if(thisV < A[i]){//pivot is between i and mid
if(target >= A[i]){
j = mid;
}
else{
if(target > thisV){
i = mid + 1;
}
else{
j = mid;
}
}
}
else{//pivot is between mid and j
if(target > thisV){
i = mid + 1;
}
else{
if(target > A[j - 1]){
j = mid;
}
else{
i = mid + 1;
}
}
}
}
return -1;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.