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;    }}