Search in Rotated Sorted Array I & II

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.

二分法，对于旋转的数组，至少有一半是已经sorted，首先判断那部分是sorted，再判断target在哪部分里。

 public class Solution {  
    //Time: O(logn) Space: O(1)  
    public int search(int[] A, int target) {  
           if (A == null || A.length == 0) {  
                return -1;  
           }  
             
           int start = 0;  
           int end = A.length - 1;  
           while (start + 1 < end) {  
                int mid = start + (end - start) / 2;  
                if (A[mid] == target) {  
                     return mid;  
                }   
                if (A[start] < A[mid]) {  
                     if (A[start] <= target && target < A[mid]) { // left are sorted  
                          end = mid;  
                     } else {  
                          start = mid;  
                     }  
                } else {  
                     if (A[mid] < target && target <= A[end]) { // right are sorted  
                          start = mid;  
                     } else {  
                          end= mid;  
                     }  
                }  
           }  
             
           if (A[start] == target) {  
                return start;  
           } else if (A[end] == target){  
                return end;  
           }  
             
           return -1;  
    }  
} 

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 {
    //Time: O(n) worst case.  Space: O(1)
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                return true;
            } else if (A[left] < A[mid]) {
                if (A[left] <= target && A[mid] > target) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (A[mid] < A[right]) {
                if (A[mid] < target && target <= A[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            } else {
                if (A[left] == A[mid]) {
                    left++;
                }
                if (A[right] == A[mid]) {
                    right--;
                }
            }
        }
        
        if (A[left] == target || A[right] == target) {
            return true;
        }
        return false;
    }
}