Search for a Range @leetcode

SearchRange.java

package leetcode.binarySearch;

/**
 * Solution: BinarySearch, two time. 2 O(logn) --> O(logn)
 * Search left bound first and then search right bound second time.
 * left: end = mid. right: start = mid. keeps we don't abandon result.
 * 
 * Take care: sequence --> target == A[start] or A[end]. left bound should check start first, right check end. 
 * 
 * @author jeffwan
 * @date Mar 9, 2014
 */
public class SearchRange {
	public int[] searchRange(int[] A, int target) {
		int[] bound = new int[2];
		int start, end, mid;
		if (A == null || A.length == 0) {
			bound[0] = bound[1] = -1;
			return bound;
		}
		
		// search the left bound, end = mid;
		start = 0;
		end = A.length - 1;
		while(start + 1 < end) {
			mid = start + (end - start) / 2;
			if (target == A[mid]) {
				end = mid;
			} else if (target < A[mid]) {
				end = mid;
			} else {
				start = mid;
			}
		}
		
		if (target == A[start]) {
			bound[0] = start;
		} else if ( target == A[end]) {
			bound[0] = end; 
		} else {
			bound[0] = bound[1] = -1;
			return bound;
		}
		
		// search the right bound, start = mid;
		start = 0;
		end = A.length - 1;
		while (start + 1 < end) {
			mid = start + (end - start) /2 ;
			if (target == A[mid]) {
				start = mid;
			} else if (target < A[mid]) {
				end = mid;
			} else {
				start = mid;
			}
		}
		
		// sequence is very important here! test case [2,2] 2 -- if start go first, result will be [0,0]
		if (target == A[end]) {
			bound[1] = end;
		} else if ( target == A[start]) {
			bound[1] = start;
		} 
		
		return bound;
	}
}