在一个旋转过的数组中搜索一个数，返回它的索引

search_in_rotated_array.cpp

class Solution1 {
public:
    /**
     * @param A: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    int search(vector<int> &A, int target) {
        int size = A.size();
        if (size == 0) {
            return -1;
        }
        int low = 0, high = size-1;
        return binarySearch(A, target, low, high);
    }
    
    int binarySearch(vector<int> &A, int target, int low, int high) {
        int mid = (low+high)/2;
        if (A[mid] == target) {
            return mid;
        }
        if (high < low) {
            return -1;
        }
        // 说明左半边是正常排序的
        if (A[low] < A[mid]) {
            if (target >= A[low] && target <= A[mid]) {
                // 要找的数字就在这半边
                return binarySearch(A, target, low, mid-1);
            } else {
                return binarySearch(A, target, mid+1, high);
            }
        } else if (A[low] > A[mid]) {
            // 说明右半边是正常排序的
            if (target >= A[mid] && target <= A[high]) {
                return binarySearch(A, target, mid+1, high);
            } else {
                return binarySearch(A, target, low, mid-1);
            }
        } else {
            if (A[mid] != A[high]) {
                return binarySearch(A, target, mid+1, high);
            } else {
                int result = binarySearch(A, target, low, mid-1);
                if (result == -1) {
                    result = binarySearch(A, target, mid+1, high);
                    return result;
                } else {
                    return result;
                }
            }
        }
        return -1;
    }
};

class Solution2 {
public:
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        if (size == 1) {
            return nums[0] == target?0:-1;
        }
        int left = 0,right = size;
        while(left != right) {
            int mid = left + (right-left)/2;
            
            if (nums[mid] == target) {
                return mid;
            } else if(nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right-1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return -1;
    }
};