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

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

题目

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

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

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

假设数组中没有重复值。

示例1：

示例2：

思路

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

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

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

我们使用递归法进行二分，每次递归进行：

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

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

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

（2）若目标值

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

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

小技巧：

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

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

代码

python实现

备注

上一篇

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

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