二分查找如何实现找出给定目标值在数组中的开始位置和结束位置-创新互联

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

代码实现

class Solution {
public:
   int left_index(vector& nums,int target)
   {
     int begin = 0;
     int end = nums.size() - 1;
     while(begin <= end)
     {
      int mid = (begin + end) / 2;
       if(nums[mid] == target)
       {
         if(mid == 0 || nums[mid - 1] < target)
         {
           return mid;
         }
         end = mid - 1;
       }
       else if(target < nums[mid])
       {
         end = mid - 1;
       }
       else if(target > nums[mid])
       {
         begin = mid + 1;
       }
     }
     return -1;
     }
     int right_index(vector& nums,int target)
     {
       int begin = 0;
       int end = nums.size() - 1;
       while(begin <= end)
       {
        int mid = (begin + end) / 2;
         if(nums[mid] == target)
         {
           if(mid == nums.size() - 1 || nums[mid + 1] > target)
           {
             return mid;
           }
           begin = mid + 1;
         }
         else if(target < nums[mid])
         {
           end = mid - 1;
         }
         else if(target > nums[mid])
         {
           begin = mid + 1;
         }
       }
       return -1;
     }   
   vector searchRange(vector& nums, int target) {
     vector result;
     result.push_back(left_index(nums,target));
     result.push_back(right_index(nums,target));
     return result;
   }
};

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。