LintCode 61 · Search for a Range.java

	public class Solution {
	/**
	* @param A: an integer sorted array
	* @param target: an integer to be inserted
	* @return: a list of length 2, [index1, index2]
	*/
	public int[] searchRange(int[] A, int target) {
	// binarySearch O(n logn) + fan out search O(n)
	// handle corner cases
	Arrays.sort(A);
	// perform a routine binarySearch
	int result = binarySearch(A, target);
	if (result == -1) {
	// if target not existed, return [-1, -1] as instructed.
	return new int[]{-1, -1};
	} else {
	// if target is located, fan out and search for the left& right limit.
	int begin = result;
	int end = result;
	while (begin > 0) {
	if (A[begin - 1] != target) {
	break;
	}
	begin--;
	}
	while (end < A.length - 1) {
	if (A[end + 1] != target) {
	break;
	}
	end++;
	}
	return new int[]{begin, end};
	}
	}
	private int binarySearch(int[] A, int target) {
	if (A == null || A.length == 0) {
	return -1;
	}
	int n = A.length;
	int begin = 0, end = A.length - 1;
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (A[mid] == target) {
	return mid;
	}
	if (A[mid] < target) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	if (A[begin] == target) {
	return begin;
	}
	if (A[end] == target) {
	return end;
	}
	return -1;
	}
	}

view raw LintCode 61 · Search for a Range.java hosted with ❤ by GitHub