Search in Rotated Sorted Array @leetcode

SearchRotatedArray.java

package leetcode.binarySearch;

/**
 * Solution: BinarySearch, split Array to two part;
 * A[start] < A[mid] --> (start,end) are sorted; 
 * A[start] > A[mid] --> (mid,end) are sorted. 
 * target >= A[start] && target <= A[end] makes sure we moves range to a sorted range step by step.
 * That means, if not in this range, move to rest part, iteratively. if yes, like general binarySearch. 
 * 
 * @author jeffwan
 * @date Mar 9, 2014
 */
public class SearchRotatedArray {
	
	public int search(int[] A, int target) {
		
		if (A == null || A.length == 0) {
			return -1;
		}
		
		int start, end, mid;
		
		start = 0;
		end = A.length - 1;
		
		while (start + 1 < end) {
			mid = start + (end - start) / 2;
			if (target == A[mid]) {
				return mid;
			}
			
			if (A[start] < A[mid]) {
				if (target >= A[start] && target < A[mid]) {
					end = mid;
				} else {
					start = mid;
				}
			} else {
				if (target > A[mid] && target <= A[end]) {
					start = mid;
				} else {
					end = mid;
				}
			}
		}
		
		if (target == A[start]) {
			return start;
		}
		
		if (target == A[end]) {
			return end;
		}
		
		return -1;
	}
}