专栏首页desperate633LeetCode 34. Search for a Range题目分析代码

LeetCode 34. Search for a Range题目分析代码

题目

给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。

如果目标值不在数组中,则返回[-1, -1]

样例 给出[5, 7, 7, 8, 8, 10]和目标值target=8,返回[3, 4]

分析

二分搜索法,先二分搜索左边界,再二分搜索右边界,注意搜索时边界的确定 搜索左边界的时候,end = mid,保证最后留下的两个数要么都等于target要么第一个小于 搜索右边界的时候,start = mid,保证最后留下的两个数,要么一个大于,要么两个都等于

代码

public class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        // write your code here
        if (A.length == 0) {
            return new int[]{-1, -1};
        }
        
        int start, end, mid;
        int[] bound = new int[2]; 
        
        // search for left bound
        start = 0; 
        end = A.length - 1;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[start] == target) {
            bound[0] = start;
        } else if (A[end] == target) {
            bound[0] = end;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }
        
        // search for right bound
        start = 0;
        end = A.length - 1;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                start = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] == target) {
            bound[1] = end;
        } else if (A[start] == target) {
            bound[1] = start;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }
        
        return bound;
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 搜索旋转排序数组题目分析代码

    假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值...

    desperate633
  • LeetCode 74. Search a 2D Matrix题目分析代码

    本题主要考察的是二分法,但是这里如何使用二分法又有不同的策略,但本质都是一样的 方法一,我们二分,先从每列的最后一个数开始,确定它的列再搜索行 方法二,就是...

    desperate633
  • LintCode 线段树系列问题(线段树的构造,线段树的构造||,线段树的查询,线段树的查询II,线段树的修改)线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

    线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

    desperate633
  • library | std cell delay 模型

    看新工艺的library 像看天书一样,多了很多内容,老驴打算挖个坑尝试去读一下lib 中每个表格所代表的意义及用途,今儿开篇。

    老秃胖驴
  • 稳扎稳打JS——执行上下文

    上下文环境的初始化在代码执行前完成 JS有三种作用域:全局作用域、函数作用域、eval作用域(不常用,不做介绍)。 在JS代码执行前,首先会对这三种作用域进行...

    大闲人柴毛毛
  • python的一些细节(2)

    想想自己写了这么久的python,其实基础的东西还是不扎实,重新学习一下廖雪峰老师的教程,有很多之前未知或者有疑惑的东西得到了解答。

    钱塘小甲子
  • python爬虫用drony转发进行抓包转发

    转载至https://www.cnblogs.com/lulianqi/p/11380794.html#l_2

    小小咸鱼YwY
  • C++ STL之查找算法

    C++STL有好几种查找算法,但是他们的用法上有很多共同的地方: 1、除了binary_search的返回值是bool之外(查找的了返回true,否则返回fal...

    用户1215536
  • Lambda 表达式有何用处?

    在Java 8之前,这个是做不到的。但是Java 8问世之后,利用Lambda特性,就可以做到了。

    Java团长
  • 数据处理 | pandas入门专题——离散化与one-hot

    在上一篇文章当中我们介绍了对dataframe进行排序以及计算排名的一些方法,在今天的文章当中我们来了解一下dataframe两个非常重要的功能——离散化和on...

    TechFlow-承志

扫码关注云+社区

领取腾讯云代金券