leetcode68-search-in-rotated-sorted-array-ii

[1],1

true
class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return bool布尔型
     */
    bool search(int* A, int n, int target) {
        // write code here
        for (int i=0;i<n;i++){
            if (A[i]==target)
                return true;
        }
        return false;
    }
};


class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return bool布尔型
     */
    bool search(int* A, int n, int target) {
        // write code here
        int first=0;
        int last=n-1;
        while (first<=last){
            int mid=first+(last-first)/2;
            if (A[mid]==target)
                return true;
            if (A[first]==A[mid]&&A[mid]==A[last]){
                first++;
                last--;
                
            }
            else if (A[first]<=A[mid])
            {
                if (A[first]<=target && target<A[mid])
                    last=mid-1;
                else 
                    first=mid+1;
                
            }
            else if (A[mid]<=A[last]){
                if (A[mid]<target && target <=A[last])
                    first=mid+1;
                else 
                    last=mid-1;
            }
        }
        return false;
    }
};