# The Problem:

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.

# Notes:

- If duplicates are allowed, we can not tell if a part is sorted or not by looking at start and end. If start is same as end, could be sorted with all duplicates, like 2222, or unsorted with turning at a duplicate, like 3123. So in this case we can not discard half as we did in Search in Rotated Sorted Array.

# Java Solution

public class Solution { public boolean search(int[] A, int target) { if(A.length==0) return false; int low = 0; int high = A.length-1; while(low <= high){ int mid = (low + high)/2; if(A[low]==target || A[high]==target || A[mid]==target){ return true; } if(A[low] < A[mid]){// former half sorted if(target>A[low] && target < A[mid]){ high = mid-1; } else{ low = mid+1; } } else if(A[low] > A[mid]){//latter half sorted if(target > A[mid] && target < A[high]){ low = mid+1; } else{ high = mid-1; } } else{//don't know low++; } } return false; } }

Advertisements