leetcode第34题，难度为medium，有序数组的查找，二分查找的变种。

Description

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1] .

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

来源： leetcode 34 find first and last position of element in sorted array

Solution

有序数组，时间复杂度 O(log n) ，很明显需要使用二分查找法，只是在实现的过程中需要额外注意一些问题。

我的解法是在找到目标数字后，向前后两个方向拓展，最终找到目标数字的两个边界，下面就是我的解法。

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> ans{-1, -1};
    if (nums.empty()) {
	return ans;
    }
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
	int mid = (left + right) / 2;
	if (nums[mid] < target) {
	    left = mid + 1;
	}
	else if (nums[mid] > target) {
	    right = mid - 1;
	}
	else {
	    int leftInnerL = left;
	    int leftInnerR = mid;
	    while (leftInnerL <= leftInnerR) {
		int leftInnerM = (leftInnerL + leftInnerR) / 2;
		if (nums[leftInnerM] < target) {
		    leftInnerL = leftInnerM + 1;
		}
		else {
		    leftInnerR = leftInnerM - 1;
		}
	    }
	    ans[0] = leftInnerL;
	    int rightInnerL = mid;
	    int rightInnerR = right;
	    while (rightInnerL <= rightInnerR) {
		int rightInnerM = (rightInnerL + rightInnerR) / 2;
		if (nums[rightInnerM] > target) {
		    rightInnerR = rightInnerM - 1;
		}
		else {
		    rightInnerL = rightInnerM + 1;
		}
	    }
	    ans[1] = rightInnerR;
	    return ans;
	}
    }
    return ans;
}

我在提交后从leetcode的solution样本中找到了下面的解法。很明显，下面这个解法看起来更加优雅。这个解法的思路是先找到左边的点，再向右拓展，找到右边的点。

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res(2, -1);
    if(nums.empty()) return res;
    int left = 0, right = nums.size() - 1;
    while (left < right) {
	int mid = left + (right - left) / 2;
	if (nums[mid] < target) left = mid + 1;
	else right = mid;
    }
    if (nums[right] != target) return res;
    res[0] = right;
    right = nums.size();
    while (left < right) {
	int mid = left + (right - left) / 2;
	if (nums[mid] <= target) left = mid + 1;
	else right= mid;
    }
    res[1] = left - 1;
    return res;
}

思考
二分查找的思路和形式都是很明确的，需要注意的是边界问题。下面让我展开来说。
注意下上面两种解法在比较 left 和 right 时，分别使用了 <= 和 < ，这个符号能够决定这个循环是死循环还是能正常退出。比较符号的选择还会影响到边界的计算问题，注意两种方法的表达式 right=mid+1 与 right=mid 合适的边界计算逻辑才能保证能够迭代出有效的结果。

由此可见，二分查找理解起来不难，但是需要注意边界问题，这很大程度影响了搜索结果的正确性。