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

一个二分查找的变种，重点是分情况讨论，讨论pivot（拐点）在i-mid区间还是mid-j区间，然后分别对应不同的i,j更新策略。

其中要注意的是，数组可能没被旋转，所以需要判断是否A[i]<A[j-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){
                return -1;//not found
            }
            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;
    }
};