public class Solution {
	public int[] searchRange(int[] A, int target) {
		int[] result = new int[] { -1, -1 };
		int left = 0;
		int right = A.length - 1;
		int middle;

		while (left <= right) {
			middle = (left + right) / 2;
			if (A[middle] > target) {
				right = middle - 1;
			} else if (A[middle] < target) {
				left = middle + 1;
			} else {
				result[0] = searchLeft(A, left, middle, target);
				result[1] = searchRight(A, middle, right, target);
				return result;
			}
		}
		return result;
	}

	private int searchLeft(int[] A, int begin, int end, int target) {
		int left = begin;
		int right = end;
		int middle;

		while (left < right) {
			middle = (left + right) / 2;
			//搜索左边界的前提是数组中已经存在target，
			//并且参数传递经来的是数组值不大于target的部分
			//故不需要检查A[middle]是否比target大
			//只需要比较A[middle]是否比target小或者相等
			if (A[middle] < target) {
				left = middle + 1;
			} else {
				return searchLeft(A, left, middle, target);
			}
		}
		return left;
	}

	private int searchRight(int[] A, int begin, int end, int target) {
		int left = begin;
		int right = end;
		int middle ;

		while (left < right) {
			middle = (left + right) / 2;
			//搜索右边界的前提是数组中已经存在target，
			//并且参数传递经来的是数组值不小于target的部分
			//故不需要检查A[middle]是否比target小
			//只需要比较A[middle]是否比target大或者相等
			if (A[middle] > target) {
				right = middle - 1;
			} else {
				//注意这比searchLeft多的一部分，
				//为了防止 A={8,9}，target=8或者 A={8,8}，target=8这一类情况
				if (middle == left && A[right] > target)
					return left;
				if (middle == left && A[right] == target)
					return right;
				return searchRight(A, middle, right, target);
			}
		}
		return left;
	}
}