LeetCode 34. Search for a Range

Given an array of integers 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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
解析：
给定一个已经排序的列表，列表按照升序排列，根据给定的数值返回下标的起始和结束位置，并且要求时间复杂度为O(log n)。比如给定序列[5, 7, 7, 8, 8, 10]和目标8，返回下标[3,4]。
根据已知条件序列有序，并且限制时间复杂度，所有首先考虑二分查找，但这里查找的结果是多个数值，而不是通常情况下的一个数值。因此可以考虑首先通过二分查找找到数值，然后从当前数值往左右扩散，找到起始和结束范围。
[cc lang=”C++”]
class Solution {
public:
vector searchRange(vector& nums, int target) {
vector result(2, -1);
if(nums.size() <= 0) return result; int low = 0; int high = nums.size()-1; while(low <= high) { int mid = (low + high) /2; if(nums[mid] == target) { int temp = mid; while(temp >= low && nums[temp] == target)
{
temp –;
}
result[0] = ++temp;
temp = mid;
while(temp <= high && nums[temp] == target) { temp ++; } result[1] = –temp; return result; }else if(nums[mid] < target) { low = mid + 1; }else { high = mid -1; } } return result; }; [/cc] 这种思路存在一个缺陷，即当最坏的情况下整个序列都是目标值的话，时间复杂度为O(n)。考虑一种完全二分查找的情况，进行两次二分查找，分别找到序列的起始位置和结束位置。二分查找直接相等的时候也向一个方向继续夹逼，如果向右夹逼，最后就会停在右边界，而向左夹逼则会停在左边界，如此用停下来的两个边界就可以知道结果。 具体代码如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);
        if(nums.size() <= 0)
            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 - 1;//等于和大于都往左移动
        }
        int temp = left;
        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 -1;
        }
        if (temp <= right){
            res[0] = temp;
            res[1] = right;
        }            
        return res; 
    }
};

思路2明显要比思路1执行速度快，仅用时4ms。
参考：
https://www.cnblogs.com/grandyang/p/4409379.html