PS：链接：没有的同学请注册
登录 - 沐枫OJhttps://www.mfstem.org/p/891 这道题目，10⁶的数据，直接循环过不了70ms的限时
那这题该怎么办呢？
O（n）不行O（logn）呢?好像可以。
看数据，保证数列为不下降序列
你有没有想到小时候猜数字的游戏
那时候的你，根本不懂怎么快速找数，每次都要猜好多次才行
接下来想，我们为什么不可以多删一点么，而且还要保证不要太亏
那我们就每次取中间呗！
接下来，我们模拟一下2，5，7，8，9，10，找5这个数据
那时间复杂度呢？
因为每次都要筛掉一半，所以时间复杂度就是O（logn）了
这种算法就叫做二分查找
从以上的过程看出来，它一定是非降序排列的
为什么呢？
如果不是按照非降序排列的，那就是只无头苍蝇，你不知道答案在你的左边还是在你的右边
我有的时候天真的觉得这样可以
好了，回归正题
这道题目可以说就是求比它小的数最大的在哪里和比它大的最小的在哪里
为什么呢，这样就是找到它的开始点和结束点了，这很容易理解吧
那我们先讲一下二分查找的模板吧
我们用找第一个大于它的数来举例
l = 1,r = n;
while(l <= r){
mid = (l + r) / 2;
if(a[mid] <= x)l = mid + 1;
else r = mid - 1;
}
printf("%lldn",l);
这就是按照上面的逻辑来的
很简单，l，r为现在查找的范围，x为要查找的数，mid为一半的位置
如果一半是小于等于要查找的数的，那么l变成mid + 1，否则r变成mid - 1
最后的代码就不用我多说了，直接套二分查找的模板就行
如果要查到的东西改变了，改变第四行的if语句里的判断条件就行了
That is THE END---------------------------------------------------------------------------------------------------------
