?🌰單峰序列題目描述

晴問算法

題目描述：

單峰序列是指，在這個序列中存在一個位置，滿足這個位置的左側（含該位置）是嚴格遞增的、右側（含該位置）是嚴格遞減的，這個位置被稱作峰頂位置。現在給定一個單峰序列，求峰頂位置的下標。

注：使用二分法實現。

輸入描述：

第一行為一個正整數𝑛（1≤𝑛≤105），表示序列的長度；

第二行按順序給出單峰序列的𝑛個元素（1≤每個元素≤106）。假設序列的下標從0開始。

數據保證不是單調序列，一定有峰頂。

思路2

?把該題轉化為尋找峰頂后一個元素，也就是該序列中第一個小于前一個元素的下標（前續解），再減1即為最終解。

? 對于二分查找閉區間[left, right]:

????????若nums[mid-1] > nums[mid] ，說明mid有可能是前續解（固定思路，先思考滿足什么條件有可能是解，反推出nums[mid-1] > nums[mid]），因為它小于前一個元素，但還需要往左檢查是否還有滿足條件的元素，因此讓rigth = mid;

????????若nums[mid -1] < nums[mid], 說明前續解在mid右側，因為它還在嚴格遞增的前半序列中，因此讓left = mid + 1;

題目說嚴格遞增與嚴格遞減，因此不存在重復的元素，不需要考慮等于的情況，直接else即可；

當left == right時，就找到了前續解，結束循環，所以進入循環條件是left < right。

? 由于數據保證序列不是單調序列，所以最終解峰頂一定不是序列中的第一個和最后一個元素，所以最終解峰頂可能取值為[1, n-1],? 因此前續解所有可能取值為[2, n], 所以查找區間初值為【2， n】。

最終解為left -1 or right -1；

//返回該序列中第一個小于前一個元素的下標（前續解）
int binarySearch(){int left = 2, right  = n, mid;while(left < right){mid = (left + right) / 2;if(nums[mid-1] > nums[mid])right = mid;elseleft = mid + 1;}return left ; // or right;
}

printf("%d\n", binarySearch() - 1);

?

思路1

對于二分查找閉區間[left, right]:

????????若nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]，說明mid是峰頂；

????????若nums[mid-1] < nums[mid], 峰頂有可能是mid,也可能在mid右側,，則讓left = mid;

????????若nums[mid] > nums[mid + 1],峰頂有可能是mid,也可能在mid左側,，則讓right = mid;

? 由于數據保證序列不是單調序列，所以峰頂（解）一定不會是第一個和最后一個，因此mid-1, mid+1一定合法，不需要檢查索引合法了，且因此峰頂（解）的所有可能取值為[1, n-1], 所以查找區間初值為【1， n-1】，當然多一個0也可以【0， n-1】

且題目說嚴格遞增與嚴格遞減，因此不存在重復的元素，不需要考慮等于的情況。

最終返回mid即可；

int left = 0, right  = n-1, mid;while(1){mid = (left + right) / 2;if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1])break;if(nums[mid-1] < nums[mid])left = mid;if(nums[mid] > nums[mid+1])right = mid;}

?