[LeetCode]Search for a Range

二分的做法，这里我们二分的时候如下处理：

• 找左边界的时候
• 如果A[mid] >= target, hi = mid - 1
• 如果A[mid] < target, lo = mid + 1
• 找右边界的时候
• 如果A[mid] <= target, lo = mid + 1
• 如果A[mid] > target, hi = mid - 1

跳出循环条件是 lo > hi，这样当循环结束时，对于左边界：

• 如果 target 在 array 中，那么 lo 对应的是左边界
• 如果 target 不在 array中
• lo 可能等于 A.length
• A[lo] 不等于 target

对于右边界来说是一样的，代码如下：

	public class Solution {
	public int[] searchRange(int[] A, int target) {
	if (A == null)
	return new int[]{-1, -1};
	int[] res = new int[2];
	res[0] = findLeft(A, target);
	res[1] = findRight(A, target);
	return res;
	}
	private int findLeft(int[] A, int target) {
	int lo = 0, hi = A.length - 1;
	while (lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if (target <= A[mid])
	hi = mid - 1;
	else
	lo = mid + 1;
	}
	return lo == A.length? -1: A[lo] == target? lo: -1;
	}
	private int findRight(int[] A, int target) {
	int lo = 0, hi = A.length - 1;
	while (lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if (target >= A[mid])
	lo = mid + 1;
	else
	hi = mid - 1;
	}
	return hi == -1? -1: A[hi] == target? hi: -1;
	}
	}

view raw search for a range v-1.java hosted with ❤ by GitHub

我们改一下 return 的策略也可以达到效果，如下代码如所示：

	public class Solution {
	public int[] searchRange(int[] A, int target) {
	if (A == null)
	return new int[]{-1, -1};
	int left = findLeft(A, target);
	int right = findRight(A, target);
	if (left > right)
	return new int[]{-1, -1};
	else
	return new int[]{left, right};
	}
	private int findLeft(int[] A, int target) {
	int lo = 0, hi = A.length - 1;
	while (lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if (target <= A[mid])
	hi = mid - 1;
	else
	lo = mid + 1;
	}
	return hi + 1;
	}
	private int findRight(int[] A, int target) {
	int lo = 0, hi = A.length - 1;
	while (lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if (target >= A[mid])
	lo = mid + 1;
	else
	hi = mid - 1;
	}
	return lo - 1;
	}
	}

view raw search for a range v-2.java hosted with ❤ by GitHub

解释：

• 在找左边界的时候，hi 是左边界左边的那一个位置
• 在找右边界的时候，lo 是右边界右边的那一个位置
• 如果 left > right的时候，target 是不在 array里的

但是以上的代码仍然有很多重复的部分，为了消除重复的代码用同样的代码就可以搜索上下边界，我们需要对策略做一个很小的修改，对于上边界的话，我们寻找上边界右边的那一个数，那么对于右边界，情况会变为，假设输入数组长n，我们在[0,n]当中进行搜索：

• 如果A[mid] <= target, lo = mid + 1
• 如果A[mid] > target, hi = mid

这样上下边界就可以共用一套代码了，只要多一个bool来标记我们这次是寻找上边界还是下边界即可。代码如下：

	class Solution {
	public:
	vector<int> searchRange(vector<int>& nums, int target) {
	int len = nums.size();
	if(!len)return {-1, -1};
	int left = search(nums, 0, len - 1, target, true);
	if(left < 0 || left >= len || nums[left] != target)return {-1, -1};
	int right = search(nums, 0, len, target, false);
	return {left, right - 1};
	}
	private:
	int search(vector<int>& num, int lo, int hi, int target, bool isLowerBound)
	{
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	if(isLowerBound)
	{
	if(num[mid] >= target)
	hi = mid;
	else
	lo = mid + 1;
	}
	else
	{
	if(num[mid] <= target)
	lo = mid + 1;
	else
	hi = mid;
	}
	}
	return lo;
	}
	};

view raw search for range_2.cpp hosted with ❤ by GitHub