Search in Rotated Sorted Array II

Medium Search in Rotated Sorted Array II

40%

Accepted

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.

public class Solution {

    /** 

     * param A : an integer ratated sorted array and duplicates are allowed

     * param target :  an integer to be search

     * return : a boolean 

     */

    public boolean search(int[] A, int target) {

        // write your code here

        if(A == null || A.length == 0) return false;

        

        int start = 0, end = A.length - 1;

        

        while(start <= end){

            int mid = (start + end) / 2;

            if(A[mid] == target) return true;

            if(A[mid] > A[start]){

                if(A[mid] > target && A[start] <= target){

                    end = mid - 1;

                } else {

                    start = mid + 1;

                }

            } else if(A[mid] < target && A[end] >= target){

                        start = mid + 1;

                    } else start++;

           

        }

        return false;

}

}