学习
实践
活动
专区
工具
TVP
写文章

每天一道算法:在有序数组中查询目标值的首尾位置

33、在有序数组中查询目标值的首尾位置

题目

给定一个升序整数数组,找到一个目标值的起始和结束位置。

如果目标值不存在,则返回 [-1,-1]。

给定一个目标值,去数组中查询这个值。如果找到,则返回索引,否则返回-1。

假设数组中没有重复值。

示例1:

示例2:

思路

在一个有序数组中查询某个目标值的位置,可以使用经典的二分法。

但是本题不仅需要查询位置,还需要查询最开始出现的位置和最晚出现的位置。

因此需要在二分法的基础上,进行修改,使得二分法可以返回一个数组,分别存放目标值的首尾位置。

我们使用递归法进行二分,每次递归进行:

1、寻找到当前数组的中位数

2、比较中位数与目标值的大小

(1)若目标值=中位数,则说明最终结果的首尾位置会分别出现在左半部分和右半部分(包括中位数本身),因此需要分别递归计算出左半部分和右半部分的首尾位置,然后取出最小的首位置和最大的尾位置,作为最终结果。

(2)若目标值

(3)若目标值>中位数,则说明最终结果的首尾位置只可能出现在右半部分,继续递归右半部分即可。

3、递归结束条件:若当前数组小于等于2,则直接对所有元素扫描一遍,返回目标值的首尾位置。

小技巧:

1、若当前数组的首尾元素相等,则由于是有序数组,因此中间所有元素也都相等。这样不必继续递归,直接根据元素值是否等于目标值即可返回结果。

2、如果没有找到首尾位置,则建议首位置返回原数组的长度,尾位置返回-1。这是因为首位置的最大值是数组长度-1,尾位置最小值是0,但凡其他递归的结果中寻找到了目标值,那么两对结果进行比较时,只需要选择较小的首位置和较大的尾位置作为最终结果即可。

代码

python实现

备注

上一篇

每天一道算法:在旋转有序数组中查询

也是对经典二分法的改造,可以参考。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181106G0VLE600?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券