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.
public class Solution { public boolean search(int[] A, int target) { /* it must be O(n), there is no salvation. Just imagine a sea of 0's with one 1 hidden somewhere. */ for(int i = 0 ; i < A.length ; i++){ if(A[i] == target) return true; } return false; } }
public class Solution { public boolean search(int[] A, int target) { /* it must be O(n), there is no salvation. Just imagine a sea of 0's with one 1 hidden somewhere. */ int left = 0; int right = A.length -1; while(left <= right){ int m = left + (right - left)/2; if(target == A[m]) return true; if(A[m] > A[left]){ if(A[left] <= target && target < A[m] ){ right = m -1; } else{ left = m +1; } } else if(A[m] < A[left]){ if(A[m] < target && target <= A[right]){ left = m + 1; } else{ right = m -1; } } else{ left++; //skip duplicate one, A[start] == A[mid] } } return false; } }