Leetcode 34 Search for a Range

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

在有序数组中找出指定元素存在的区间。

两次二分,找到等于target和大于target的位置就行了

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result(2,-1);
        int l=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
        int r=upper_bound(nums.begin(),nums.end(),target)-nums.begin();
        if(l!=r)
        {
            result[0]=l;
            result[1]=r-1;
        }
        return result;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 16 3Sum Closest

    Given an array S of n integers, find three integers in S such that the sum is c...

    triplebee
  • Leetcode 238. Product of Array Except Self

    Given an array of n integers where n > 1, nums, return an array output such th...

    triplebee
  • Leetcode 81 Search in Rotated Sorted Array II

    Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed...

    triplebee
  • Leetcode 算法 - 1. Two Sum

    这是我解的第一道题, 当时就懵比了, 写了若干方法均超时了. 最后到网上搜索的答案. 需要用哈希表, python 字典其实就是哈希表的实现. 感受下哈希表的使...

    用户1416054
  • 377. Combination Sum IV

    有一个不包含重复值的正整数数组nums,问从数组中选择几个数,其和为target,这样的数的组合有几种?

    眯眯眼的猫头鹰
  • 杭电5178 (二分练习!)

    pairs John has n points on the X axis, and their coordinates are (x[i],0),(i=0,...

    杨鹏伟
  • 归并排序

    #include<stdio.h> void MergeArray(int first,int mid,int last,int a[]) { int...

    用户1624346
  • 每天一道leetcode18-四数之和

    乔戈里
  • 我的MOOC之路(二)——七周学会做搜索引擎

    2013年秋天,我开始学习Python。一个转了专业的程序员,干嘛30多岁还要去学一门新的编程语言呢?因为看到了痛点,学生的痛点。

    王树义
  • 互联网公司为什么要学C语言?

    互联网作为当下最有“钱景”的行业之一,那么今天我们就聊聊,C语言这个做互联网行业影响究竟有多大呢?

    诸葛青云

扫码关注云+社区

领取腾讯云代金券