067. Search for a Range

[ender233]

针对这种极端情况，我在最开始加上一句判断：
if (A[0] == A[n-1] && A[0] == target) return vector{0, n-1};

仅仅去掉两个元素, 时间复杂度应该没有变吧, 比如元素1和n-2闭区间都是目标元素, 复杂度也是O(n)了
这道题倒是可以实现时间复杂度为2logn

1. 实现一个正常的二分查找, 用于定位是否有目标元素 以及 定位位置iPos
2. 封装两个二分查找变种, 在[0, iPos] [iPos, n)分别找到(target-1) (target+1)应该插入的位置, 这两个位置就是最后要找到的区间.
   这样最坏情况, 步骤1和2各用掉logn时间. 类似这样:

int iPos = binSearch(A, target, 0, n);
int leftPos = binSearch_l(A, target-1, 0, iPos);
int rightPos = binSearch_r(A, target+1, iPos+1, n);

[pezy]

@ender233 今晚才细看了下题目。

仅仅去掉两个元素

貌似你好像误解了这句话的作用。。。首先，这是一个排序过的数组对吗？那么如果首尾相等的话：

5 * * * * 5

你说说看，有没有可能出现你说的那种情况？

if 目标 > 5

5 7 7 7 7 5 // 违反了排序

else if 目标 < 5

5 3 3 3 3 5 // 违反了排序

综上，如果首尾相等，那么只能是：

5 5 5 5 5 5

如果 5 是目标，那么可以直接返回对吗？

[ender233]

那比如 这种呢, target为7

17777777777777779

[pezy]

@ender233

感谢~ 看来误解的是我。非常抱歉，这次完全理解你的意思，以及非常认同你的思路了。

但具体实现的时候，还是偷了点懒，效率应该是赶不上你那个的，但比我以前那个，不知道高到哪里去了。 😄

希望日后能继续提供更好的思路，非常感谢~ 👍

[ender233]

哈哈 你这样实现， 既简洁又高效了. 时间复杂度是一个数量级.

能写出你那些通俗易懂的答案和解析， 我还差的远.

该感谢的是我. 经常来你这取经.