建設項目環(huán)境影響登記網(wǎng)站湖北,成都互聯(lián)網(wǎng)公司數(shù)量排名,cvm服務器做網(wǎng)站,微網(wǎng)站和手機網(wǎng)站的區(qū)別1.上篇提到無序數(shù)組用sort排序再二分#xff0c;感覺被自己蠢笑了#xff0c;因為sort函數(shù)的時間復雜度O(nlogn),二分查找是(logn),所以這個是無意義的。然后上一篇sort函數(shù)用法也寫錯了#xff0c;應該是sort(a1, a n1)#xff0c;因為初始下標為1#xff0c;注意一下就…1.上篇提到無序數(shù)組用sort排序再二分感覺被自己蠢笑了因為sort函數(shù)的時間復雜度O(nlogn),二分查找是(logn),所以這個是無意義的。然后上一篇sort函數(shù)用法也寫錯了應該是sort(a1, a n1)因為初始下標為1注意一下就行2.然后這里補充一下有一個極值時怎么用二分查找假如有7個數(shù)字1 2 3 4 3 2 1我們想要用二分找峰值但是它不是一個有序的數(shù)列所以我們可以做一下變形我們先假定一個函數(shù)yx^2我們對它求導后當y0時x0,也就是說此時取得極值也是峰值咋們再回到我們這個數(shù)列也可以把它看作一個函數(shù)其中每2個相鄰的數(shù)的dx每個相鄰數(shù)下標差為1dyarr[i]-arr[i-1],dy/dx就是此時的導數(shù)值也可以叫變化率那么我們此時得到一個新的數(shù)組 1 1 1 -1 -1 -1這里就是一個從正到負的有序數(shù)組了我們定義兩個變量 int cur,pre,所以就有當前數(shù)-前一個數(shù)0時假設此時mid5那么就是說arr[5]-arr[4]0時找到峰值下標mid-1。以下是代碼實現(xiàn)#includeiostream #includealgorithm using namespace std; int istop(int cur, int pre) { return cur - pre 0 ;//當前數(shù)字減去前一個數(shù)字 } int main() { int n7;//n為數(shù)組長度 int a[100];//存儲輸入元素 int ans -1; //初始化目標值下標 for (int i 1; i n; i) { //用for循環(huán)輸入每一個元素 cin a[i]; } int l 1, r 7;//l是數(shù)組左端點r是右端點 while (l r) { //當lr時說明此時已經(jīng)找到目標元素或者沒有目標元素 int mid (l r) / 2; //中間點下標 if (istop(a[mid],a[mid-1])) { ans mid-1; r mid - 1;//繼續(xù)向左找更早的位置此時數(shù)字可能重復; } else { l mid 1; //向右繼續(xù)查找 } } if (ans -1) { cout 元素x不在數(shù)組中 endl; } else { cout ans endl; } return 0; }3.如果是找極小值把return cur - pre 0改為return cur - pre 0,原理是一樣的