帝国做的网站根目录网站icp备案

帝国做的网站根目录,网站icp备案,中小型网站建设行情,地区性门户网站是什么意思1.上篇提到无序数组用sort排序再二分#xff0c;感觉被自己蠢笑了#xff0c;因为sort函数的时间复杂度O(nlogn),二分查找是(logn),所以这个是无意义的。然后上一篇sort函数用法也写错了#xff0c;应该是sort(a1, a n1)#xff0c;因为初始下标为1#xff0c;注意一下就…1.上篇提到无序数组用sort排序再二分感觉被自己蠢笑了因为sort函数的时间复杂度O(nlogn),二分查找是(logn),所以这个是无意义的。然后上一篇sort函数用法也写错了应该是sort(a1, a n1)因为初始下标为1注意一下就行2.然后这里补充一下有一个极值时怎么用二分查找假如有7个数字1 2 3 4 3 2 1我们想要用二分找峰值但是它不是一个有序的数列所以我们可以做一下变形我们先假定一个函数yx^2我们对它求导后当y0时x0,也就是说此时取得极值也是峰值咋们再回到我们这个数列也可以把它看作一个函数其中每2个相邻的数的dx每个相邻数下标差为1dyarr[i]-arr[i-1],dy/dx就是此时的导数值也可以叫变化率那么我们此时得到一个新的数组 1 1 1 -1 -1 -1这里就是一个从正到负的有序数组了我们定义两个变量 int cur,pre,所以就有当前数-前一个数0时假设此时mid5那么就是说arr[5]-arr[4]0时找到峰值下标mid-1。以下是代码实现#includeiostream #includealgorithm using namespace std; int istop(int cur, int pre) { return cur - pre 0 ;//当前数字减去前一个数字 } int main() { int n7;//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) { //当lr时说明此时已经找到目标元素或者没有目标元素 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,原理是一样的