LeetCode 34

概述

​ 题目给定一个升序数组，又要求时间复杂度O(log n)算法，考虑二分解决

思路1

• 一般二分查找，只能找到其中一个target，现在要找target在数组中的开始位置和终止位置，考虑每次找到后将数组分成左右两个，那么开始、终止位置也就可能在左右两边。

• 对左右两边，可以继续二分查找，直到找不到停止。到这里，考虑递归思想。

• 对于递归函数，返回值应该就是最终的结果，还要注意临界条件。

  class Solution {
  public:
       vector<int> find(vector<int>& nums,int target,int l,int r){	//这里l,r就是用来记录最终结果用
           while(r>=l){  
           	int mid=(l+r)/2;
              if(nums[mid]>target)
                  r=mid-1;
              else if(nums[mid]<target)
                  l=mid+1;
              else{	//找到一个边界target
                  if(nums[l]!=target)	//如果最左边不等于target
                      l=find(nums,target,l+1,mid)[0];	//左边往后移动，只取数组第一个结果
                  if(nums[r]!=target)	//如果最右边不等于target
                      r=find(nums,target,mid,r-1)[1];	//右边后前移动
                  return vector<int>{l,r};
              }
          }
           //如果找不到 
          return  vector<int>{-1,-1};
      }
      vector<int> searchRange(vector<int>& nums, int target) {
          return find(nums,target,0,nums.size()-1);
      }
  };

思路二

• 考虑到传入的是vector类型，而c++STL中存在一个二分查找的算法equal_range,可以使用该函数
• equal_range：试图在已排序的[first,last)中寻找value，它返回一对迭代器i和j，其中i是在不破坏次序的前提下，value可插入的第一个位置（亦即lower_bound），j则是在不破坏次序的前提下，value可插入的最后一个位置（亦即upper_bound）

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto bound=equal_range(nums.begin(),nums.end(),target);
        if(bound.first==bound.second)   return {-1,-1};	//两个迭代器 first second
        return {(int)(bound.first-nums.begin()),(int)(bound.second-nums.begin())-1};	//通过迭代器相减 q
    }
};