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.
|
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)$.