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 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

Java实现解析IP地址的方法,给出一串数字,生成正确的IP地址

给定一个只包含数字的字符串,通过方法返回所有可能的有效的IP地址组合。 例如:给出“25525511135”,返回(“255.255.11.135”、“255....

31990
来自专栏WD学习记录

牛客网 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在...

9930
来自专栏数据处理

leetcode222求完全二叉树节点个数

37940
来自专栏IT笔记

ArrayList和LinkedList的区别

首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

33180
来自专栏大闲人柴毛毛

剑指offer代码分析——面试题13在O(1)内删除链表结点

本题详细解析都已在代码中注释了: /** * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p * @author chibozhou *...

38250
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

9840
来自专栏zhisheng

SimpleDateFormat 如何安全的使用?

看到这条我立马就想起了我实习的时候有个项目里面就犯了这个错误,记得当时是这样写的:

11010
来自专栏猿人谷

顺序线性表

线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置...

24050
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

15310
来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

35570

扫码关注云+社区

领取腾讯云代金券