翻译

给定一个整型已排序数组，找到一个给定值在其中的起点与终点。你的算法复杂度必须低于O(logn)。如果目标在数组中不会被发现，返回[-1, -1]。例如，给定[5, 7, 7, 8, 8, 10]，目标值为8，返回[3, 4]。

原文

Given a sorted array of integers, 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].

代码

class Solution {public:    vector
     
       searchRange(vector
      
        &nums, int target) {        vector
       
         res;        int l = 0, r = nums.size() - 1;        if(nums.size() <= 0) {            res.push_back(-1);            res.push_back(-1);            return res;             } else if(nums.size() == 1) {            if(nums[0] == target) {                res.push_back(0);                res.push_back(0);                return res;            } else {                res.push_back(-1);                res.push_back(-1);                return res;            }        }        while(l <= r) {            if(nums[l] < target) {                ++l;            }             if(nums[r] > target) {                --r;            }            if(nums[l] == target && nums[r] == target) {                res.push_back(l);                res.push_back(r);                return res;            }        }        res.push_back(-1);        res.push_back(-1);        return res;    }};
       
      
     

随手写的，虽然能通过，不过还是看看大神的解法来提高自己。

class Solution {private:    int binarySearchLow(vector
     
      & nums, int target, int begin, int end)    {        if(begin > end) return begin;        int mid = begin + (end - begin) / 2;        if(nums[mid] < target) return binarySearchLow(nums, target, mid + 1, end);        else return binarySearchLow(nums, target, begin, mid - 1);    }    int binarySearchUp(vector
      
       & nums, int target, int begin, int end)    {        if(begin > end) return end;        int mid = begin + (end - begin) / 2;        if(nums[mid] > target) return binarySearchUp(nums, target, begin, mid - 1);        else return binarySearchUp(nums, target, mid + 1, end);    }public:    vector
       
         searchRange(vector
        
         & nums, int target) {        vector
         
           res(2, -1);        if(nums.empty()) return res;        int high = binarySearchUp(nums, target, 0, nums.size() -1);        int low = binarySearchLow(nums, target, 0, nums.size() - 1);        if(high >= low)        {            res[0] = low;            res[1] = high;            return res;        }        return res;    }};