Leetcode: Search in Rotated Sorted Array I&II

Search in Rotated Sorted Array 

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

 public int search(int[] A, int target) {
        if(A == null || A.length ==0) return -1;
        
        int start=0;
        int end = A.length-1;
        int mid;

        
        while (start <= end){// Note: <=
            // avoid overflow if using (start+end)/2
            mid = start + (end-start)/2;
            
            if(A[mid] == target) return mid;
            
            if(A[start] <= A[mid]){
           // from start to mid must be sorted ascending
                if(target>=A[start] && target<A[mid]){
                    end = mid-1;// no duplicate, so can safely -1
                }
                else
                    start = mid+1;
            }
            else{//from mid to end must be sorted and ascending
                if(target>A[mid] && target<=A[end]){
                    start = mid+1;
                }
                else
                    end = mid-1;
            }
            
        }
        
        return -1;         
    }

To avoid some noisy <= or >=, rewrite code as

public int search(int[] A, int target) {
        if(A == null || A.length ==0) return -1;
        
        int start=0;
        int end = A.length-1;
        int mid;

        
        while (start <= end){// Note: <=
            if(A[start] == target) return start;
            if(A[end] == target) return end;
            // avoid overflow if using (start+end)/2
            mid = start + (end-start)/2;
            
            if(A[mid] == target) return mid;
            // from start to mid must be sorted ascending
            if(A[start] <= A[mid]){
                if(target>A[start] && target<A[mid]){
                    end = mid-1;// no duplicate, so we can safely -1
                }
                else
                    start = mid+1;
            }
            else{//from mid to end must be sorted and ascending
                if(target>A[mid] && target<A[end]){
                    start = mid+1;
                }
                else
                    end = mid-1;
            }
            
        }
        
        return -1;       
    }

If duplicates are allowed, that would be question II

My First Solution. Finally give up. Doesn't  work well.

  public boolean search(int[] A, int target) {
        if(A == null || A.length ==0) return false;
       
        int start=0;
        int end = A.length-1;
        int mid;

        while (start < end){// Note: <=
            if(A[start] == target) return true;
            if(A[end] == target) return true;
           
            mid = start + (end-start)/2;// avoid overflow if using (start+end)/2
           
            if(A[mid] == target) return true;
           
            if(A[start] < A[mid]){// from start to mid must be sorted ascending
               
                if(target>A[start] && target<A[mid]){
                    while(A[mid]==A[mid-1] && mid>start){mid--;}
                    end = mid-1;// no duplicate, so we can safely -1
                }
                else{
                    while(A[mid]==A[mid+1] && mid<end){mid++;}
                    start = mid+1;
                }
            }
            else if(A[start] > A[mid]){//from mid to end must be sorted and ascending
                if(target>A[mid] && target<A[end]){
                    while(A[mid]==A[mid+1] && mid<end){mid++;}
                    start = mid+1;
                }
                else{
                    while(A[mid]==A[mid-1] && mid>start){mid--;}
                    end = mid-1;
                }
            }
            else{// A[start] == A[mid]
                if(mid == start) {start++;}
                else{
                    //three possibilities, e.g. 11113 or 1131 or 1231111
                    if(A[start] ==A[end]){// something like 1231111 or 111113
                    //OK!!!!!Give up here. Cannot proceed@!
                        while(A[mid]==A[mid-1] && mid>start){mid--;}
                        end = mid-1;
                    }
                    else{
                        while(A[mid]==A[mid+1] && mid<end){mid++;}
                        start = mid+1;
                    }
                }
            }
           
        }
       
        if(A[start] == target) return true;
        else return false; 
    }

 Next solution. Simply add " while(A[start] ==A[end] && start != end) end--;" to solve it.


public class Solution {
    public boolean search(int[] A, int target) {
       
        if(A == null || A.length ==0) return false;
       
        int start=0;
        int end = A.length-1;
        int mid;

       
        while (start <= end){// Note: <=
       
            while(A[start] ==A[end] && start != end) end--;
           
            if(A[start] == target) return true;
            if(A[end] == target) return true;
           
            mid = start + (end-start)/2;// avoid overflow if using (start+end)/2
           
            if(A[mid] == target) return true;
           
            if(A[start] <= A[mid]){// from start to mid must be sorted ascending
                if(target>A[start] && target<A[mid]){
                    end = mid-1;// no duplicate, so we can safely -1
                }
                else
                    start = mid+1;
            }
            else{//from mid to end must be sorted and ascending
                if(target>A[mid] && target<A[end]){
                    start = mid+1;
                }
                else
                    end = mid-1;
            }
           
        }
       
        return false; 
       
       
    }
 
}