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.

//This question is the advanced version of question "Search in Rotated Sorted Array I" //The key to solve it is to determine when to use linear search algorithm rather than an binary search one. //When A[start] == A[end - 1], we have to search all the cases between [start, mid), and [mid, end) //because we don't know where the pivot is. We can't shrink the search range unless A[mid] != A[start] and A[mid] != A[end - 1], which is a small possible incident. class Solution { public: bool search(vector A,int target) { int n = A.size(); if(n == 0){ return false; } return _search(A, 0, n, target); } bool _search(vector A, int start, int end, int target){ //base case if(end - start == 1){ return A[start] == target; } int mid = (start + end) / 2; if(A[start] == A[end - 1]){ //linear search return _search(A, start, mid, target) || _search(A, mid, end, target); } else{ //binary search if(A[start] < A[end - 1]){ if(target < A[mid]){ return _search(A, start, mid, target); } else{ return _search(A, mid, end, target); } } //pivot is between start and end - 1 else{ if(A[mid] >= A[start]){ if(target >= A[mid]){ return _search(A, mid, end, target); } else{ if(target <= A[end - 1]){ return _search(A, mid, end, target); } else{ return _search(A, start, mid, target); } } } //mid is at the right of pivot else{ if(target >= A[start]){ return _search(A, start, mid ,target); } else{ if(target < A[mid]){ return _search(A, start, mid, target); } else{ return _search(A, mid, end, target); } } } } } } };