34. Search for a Range-白红宇

34. Search for a Range

阅读量：6476 次

发布时间：2019-06-23

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

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].

解析

关于二分法的查找延伸的问题，细节要注意

注意使用stl的函数实现，在[first,last)区间查找

class Solution_34 {public:    int findUpBound(vector
    
     & nums, int target) //找上边界    {        int low = 0, high = nums.size() - 1;        if (nums.back()
     
      > 1;            if (nums[mid]<=target)   /// 向右夹逼，找到右边界            {                low = mid + 1;            }            else            {                high = mid - 1;            }        }        return high; //向右夹逼，返回high    }    int findDownBound(vector
      
       & nums, int target) // 找下边界    {        int low = 0, high = nums.size() - 1;        if (nums.front()>target)        {            return -1;        }        while (low<=high)        {            int mid = (low + high) >> 1;            if (nums[mid]

searchRange(vector

& nums, int target) { //找到target的上下边界 vector

vec(2, -1); if (nums.size() == 0 || nums.front()>target || nums.back()

searchRange2(int A[], int n, int target) { vector

vec(A,A+n); //初始化 return searchRange1(vec, target); } vector

searchRange1(vector

& nums, int target) { //找到target的自身上下边界，非严格上下界 vector

vec(2, -1); if (nums.size() == 0||nums.front()>target||nums.back()

temp; //针对 upper_bound the objects in the range [first,last) are accessed. 本身传入的迭代器end().就是指向下一个位置 auto range=equal_range(nums.begin(), nums.end(), target); //返回的是两个迭代器,解引用得到值 if (*range.first!=target||*(range.second-1)!=target) { return vec; } vec[0]=(range.first-nums.begin()); //stl: distance()计算迭代器之间的距离 vec[1]=(range.second - nums.begin()-1); return vec; }};

题目来源

转载地址：http://kelko.baihongyu.com/