lintcode 搜索区间

作者: yzawyx0220 | 来源:发表于2017-01-04 16:10 被阅读82次

给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中,则返回[-1, -1]
样例
给出[5, 7, 7, 8, 8, 10]和目标值target=8,
返回[3, 4]
题目链接:http://www.lintcode.com/zh-cn/problem/search-for-a-range/
通过二分查找找到起始位置和结束位置,一定要考虑到数组为空的情况,不然A[i-1]会产生runtime error

class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
public:
    vector<int> searchRange(vector<int> &A, int target) {
        // write your code here
        vector<int> res = {-1,-1};
        if (A.empty()) return res;
        int i = 0,j = A.size();
        while (i < j) {
            int mid = (i + j) / 2;
            if (A[mid] >= target) j = mid;
            else i = mid + 1;
        }
        if (A[j] == target) res[0] = j;
        i = 0,j = A.size();
        while (i < j) {
            int mid = (i + j) / 2;
            if (A[mid] > target) j = mid;
            else i = mid + 1;
        }
        if (A[i - 1] == target) res[1] = i - 1;
        return res;
    }
};    

相关文章

  • lintcode 搜索区间

    给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。如果目标值不在数组中,则返回[...

  • lintcode 二叉查找树中搜索区间

    给定两个值 k1 和 k2(k1 < k2)和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节...

  • 搜索区间

    描述 给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。如果目标值不在数组中,则...

  • LintCode - 插入区间(普通)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 难度:容易 要求: 给出一个无重叠的按照区间起始端点排序的区...

  • 搜索年份区间

    对应的武将配置表的POS字段,表示武将每个时间段出现的城市位置,对照武将信息查看 属性说明 序号 序号 开始年份 ...

  • LintCode 156. 合并区间

    描述给出若干闭合区间,合并所有重叠的部分。样例 思路2同思路1首先对原数组进行排序,然后遍历整个数组,如果前一个元...

  • LintCode 156-合并区间

    分析 注意细节处理就好

  • LintCode 30-插入区间

  • mySql 操作语句

    关键词模糊搜索 日期区间查询

  • 二分查找

    开区间与闭区间开区间——意味着是开的,也就是没有端点 ( )闭区间——意味着关闭的,也就是有端点 [ ] 搜索区...

网友评论

    本文标题:lintcode 搜索区间

    本文链接:https://www.haomeiwen.com/subject/jnnovttx.html