Search in Rotated Sorted Array II @leetcode

SearchRotatedArray2.java

package leetcode.binarySearch;

/**
 * Solution: Binary Search, consider A[start] == A[mid] based on Search a Rotated Array I
 * 
 * The most important problem we need to consider the situation A[mid] = A[start] which we didn't consider in
 * search rotated sorted array I. We can't simply user A[start] <= A[mid], Actually we can't make judgment. 
 * A[start] = A[mid] can't make sure, so start++. because A[start] == A[mid], it will not skip the target, just
 * skip the useless number 
 * 	
 * @author jeffwan
 * @date Mar 9, 2014
 */
public class SearchRotatedArray2 {
	public boolean search(int[] A, int target) {
		if (A == null || A.length == 0) {
			return false;
		}
		int start, end, mid;
		
		start = 0;
		end = A.length - 1;
		
		while (start + 1 < end) {
			mid = start + (end - start) / 2;
			if (target == A[mid]) {
				return true;
			}
			
			if (A[start] < A[mid]) {
				if (target >= A[start] && target <= A[mid]) {
					end = mid;
				} else {
					start = mid;
				}
			} else if (A[start] > A[mid]){
				if (target >= A[mid] && target <= A[end]) {
					start = mid;
				} else {
					end = mid;
				}
			} else {
				start ++;
			}			
		} //end while
		
		if (target == A[start]) {
			return true;
		}
		
		if (target == A[end]) {
			return true;
		}
		
		return false;
	}
}