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.

Analysis

This problem is similar to “Search in Rotated Sorted Array”. But there could be duplicates.

In problem “Search in Rotated Sorted Array”, we compare A[left] with A[mid] to determine which part does not contains the rotate pivot. But in this problem, A[left] could be equal to A[mid]. To solve this problem, we can let just add 1 to left when we face A[left] == A[mid] and continue the algorithm.

public class Solution {    public boolean search(int[] A, int target) {        int start = 0;        int end = A.length - 1;        while (start <= end) {            int mid = (start + end) / 2;            if (A[mid] == target)                return true;            if (A[start] < A[mid]) {                if (target >= A[start] && target < A[mid])                    end = mid - 1;                else                    start = mid + 1;            } else if (A[start] > A[mid]) {                if (target > A[mid] && target <= A[end])                    start = mid + 1;                else                    end = mid - 1;            } else                start++;        }        return false;    }}

Complexity

The worst case complexity will become  O(n) O(n).