Follow up for “Search in Rotated Sorted Array”:

What ifduplicatesare 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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)$.