pic

Search In Rotated 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.

分析

题目的意思是：如果一个有序的数组从中间分割，将左边部分移到右边部分后面。在这个新数组中查找一个数值，如果找到，返回数组索引，找不到返回-1.数组的元素都是不重复的。

若是从头遍历需要O(n)的复杂度，而二分查找则需要O(logN)，显然使用二分查找。
Note：难点在于确定左右边界。

Code

class Solution {
    public:
        /* 
         * 使用二分查找，但是需要确定好左右边界left，right。
         * */
        int search(int A[], int n, int target) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(!n)  return -1;
            if(n==1) 
            {
                if(A[0] == target) return 0;
                return -1;
            }
            int left=0, right=n-1;
            int middle;
            while(left < right)
            {
                middle = left + ((right-left)>>1);
                if(A[middle] == target)
                    return middle;
                if(A[middle] > A[left])
                {
                    if( A[left] == target)
                        return left;
                    if(A[left] < target && A[middle] > target)
                        right = middle - 1;
                    else
                        left = middle + 1;
                }
                else
                {
                    if(A[right] == target)
                        return right;
                    if(A[middle] < target && target < A[right])
                        left = middle + 1;
                    else
                        right = middle - 1;
                }
            }
            if(left == right && A[left] == target)
                return left;
            return -1;
        }
};

pic