对上篇二分查找的纠正和补充

1.上篇提到无序数组用sort排序再二分，感觉被自己蠢笑了，因为sort函数的时间复杂度O(nlogn),二分查找是(logn),所以这个是无意义的。然后上一篇sort函数用法也写错了，应该是sort(a+1, a + n+1)，因为初始下标为1，注意一下就行

2.然后这里补充一下有一个极值时怎么用二分查找，假如有7个数字：1 2 3 4 3 2 1，我们想要用二分找峰值，但是它不是一个有序的数列，所以我们可以做一下变形，我们先假定一个函数y=x^2，我们对它求导后，当y`=0时，x=0,也就是说此时取得极值，也是峰值，咋们再回到我们这个数列，也可以把它看作一个函数，其中每2个相邻的数的dx=每个相邻数下标差为1，dy=arr[i]-arr[i-1],dy/dx就是此时的导数值，也可以叫变化率

那么我们此时得到一个新的数组 1 1 1 -1 -1 -1，这里就是一个从正到负的有序数组了，我们定义两个变量 int cur,pre,所以就有当前数-前一个数<0时，假设此时mid=5，那么就是说arr[5]-arr[4]<0时，找到峰值下标mid-1。以下是代码实现：

#include<iostream> #include<algorithm> using namespace std; int istop(int cur, int pre) { return cur - pre <0 ;//当前数字减去前一个数字 } int main() { int n=7;//n为数组长度 int a[100];//存储输入元素 int ans = -1; //初始化目标值下标 for (int i = 1; i <= n; i++) { //用for循环输入每一个元素 cin >> a[i]; } int l = 1, r =7;//l是数组左端点，r是右端点 while (l <= r) { //当l>r时，说明此时已经找到目标元素或者没有目标元素 int mid = (l + r) / 2; //中间点下标 if (istop(a[mid],a[mid-1])) { ans = mid-1; r = mid - 1;//继续向左找更早的位置，此时数字可能重复; } else { l = mid + 1; //向右继续查找 } } if (ans == -1) { cout << "元素x不在数组中" << endl; } else { cout << ans << endl; } return 0; }

3.如果是找极小值：把return cur - pre <0改为return cur - pre >0,原理是一样的