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.
My analysis:
It metrics if we really master the idea underlying binary search.
What the duplicates bring into this problem is that:
For checking condition: if (A[low] <= A[mid])
What if low and mid not equal to 0, but A[low] and A[mid] have the same value ?
In this situation, we no longer be able to decide to iterate on which partion any more. We can only gain the information of ordered paration from the comparsion from A[low] and A[mid].
How to solve this problem?
? 1. directly move the ptr of mid, mid ++ or mid --. meaningless!!!
cause:
while (low <= high) {
mid = (low + high) / 2;
? 2. move the ptr of high, high--. wrong!!!
cause:
we write our checking condition based on A[low], we only knwo A[low] == A[mid] at present.
3. move the ptr of low. absoultely right!!! This could lead following effects:
a. move low ptr, reducing the range need to search. (since the current is not the target, we could discard it!)
b. move mid ptr. mid = (low + high) / 2. It make sense too, since A[mid] != target, we could discard it.
My solution:
public class Solution { public int search(int[] A, int target) { if (A.length == 0) return -1; int low = 0; int high = A.length - 1; int mid = -1; while (low <= high) { mid = (low + high) / 2; if (A[mid] == target) return mid; if (A[low] <= A[mid]) { //either left partion or right partion is perfectly sorted. if (A[low] <= target && target < A[mid]) high = mid - 1; else low = mid + 1; } else{ if (A[mid] < target && target <= A[high]) low = mid + 1; else high = mid - 1; } } return -1; } }