本文共 2021 字，大约阅读时间需要 6 分钟。

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 = 8Output: [3,4]

Example 2:

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

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non decreasing array.
• -10^9 <= target <= 10^9

题意：在排序数组中确定数字 target 出现的左右边界。

解法1 STL

用STL的二分查找函数。代码如下：

class Solution {
   public:    vector
   
     searchRange(vector
    
     & nums, int target) {
            int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();        int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;        if (left > right) return {
   -1, -1};        return vector
     
      {
   left, right};    }};
     
    
   

解法2 手写二分上下界函数

class Solution {
   private:     //找到第一个>=v的元素的位置    int lowerBound(vector
   
    & A, int x, int y, int v) {
           while (x < y) {
               int m = x + (y - x) / 2;            if (A[m] >= v) y = m;            else x = m + 1;        }        return x;    }    //找到第一个>v的元素的位置    int upperBound(vector
    
     & A, int x, int y, int v) {
           while (x < y) {
               int m = x + (y - x) / 2;            if (A[m] > v) y = m;            else x = m + 1;        }        return x;    }public:    vector
     
       searchRange(vector
      
       & nums, int target) {
           if (nums.empty()) return {
   -1, -1}; //特判空        int n = nums.size();        int first = lowerBound(nums, 0, n, target); //第一个<=        if (first >= n || nums[first] != target) return vector
       
        {
   -1, -1}; //特判不存在        int last = upperBound(nums, 0, n, target); //第一个<         return vector
        
         { first, last - 1}; }};
        
       
      
     
    
   

运行效率如下：

执行用时：20 ms, 在所有 C++ 提交中击败了74.62% 的用户内存消耗：13.5 MB, 在所有 C++ 提交中击败了67.57% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108372747 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！