Leetcode–Search in Rotated Sorted Array II

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:

  1. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s