Search Insert Position @leetcode

SearchInsert.java

package leetcode.binarySearch;

/**
 * Solution: BinarySearch, complexity is to handle different result if target could not be found.
 * target < A[0] --> 0(start)
 * target > A[start] && target < A[end] --> start + 1  or end
 * target > A[end] -- end + 1
 * target = A[start] --> start
 * target = A[end] --> end  
 * We could combine these situations to following codes.
 * 
 * @author jeffwan
 * @date Mar 9, 2014
 */
public class SearchInsert {
	public int searchInsert2(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;
			} else if (target < A[mid]) {
				end = mid;
			} else {
				start = mid;
			}
		}

		// if contains return  ---> don't need to use if-else
		if (target <= A[start]) {
			return start;
		}

		if (target > A[end]) {
			return end + 1;
		}
		
		return end;
	}
}