LeetCode Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

思路：每次判断A[left],A[mid],A[right]的关系，然后找到确定是递增的部分接着二分，也有特殊情况就是left++,right--

class Solution {
public:
    bool search(int A[], int n, int target) {
        int left = 0, right = n-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return true;
            if (A[left] < A[mid]) {
                if (A[left] <= target && target < A[mid])
                    right = mid - 1;
                else left = mid + 1;
            } else if (A[mid] < A[right]) {
                if (A[mid] < target && target <= A[right])
                    left = mid + 1;
                else right = mid - 1;
           } else if (A[left] == A[mid]) left += 1;
           else if (A[right] == A[mid]) right -= 1;
        }

        return false;
    }
};

LeetCode Search in Rotated Sorted Array II

原文：http://blog.csdn.net/u011345136/article/details/44975453