文章目錄

• 1、山脈數組的峰頂索引
• 2、尋找峰值
• 3、尋找旋轉排序數組中的最小值
• 4、LCR 點名

1、山脈數組的峰頂索引

符合下列屬性的數組 arr 稱為 山脈數組 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
給你由整數組成的山脈數組 arr ，返回滿足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下標 i 。
你必須設計并實現時間復雜度為 O(log(n)) 的解決方案。

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int n=arr.size();int left=0;int right=n-1;while(left<right){int mid=left+(right-left+1)/2;//找右端點要加一的if(arr[mid]>=arr[mid-1])left=mid;elseright=mid-1;}return left;}
};

2、尋找峰值

峰值元素是指其值嚴格大于左右相鄰值的元素。
給你一個整數數組 nums，找到峰值元素并返回其索引。數組可能包含多個峰值，在這種情況下，返回 任何一個峰值 所在位置即可。
你可以假設 nums[-1] = nums[n] = -∞ 。
你必須實現時間復雜度為 O(log n) 的算法來解決此問題。

class Solution {
public:int findPeakElement(vector<int>& nums) {int n=nums.size();int left=0;int right=n-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>=nums[mid-1])left=mid;elseright=mid-1;}return left;}
};

3、尋找旋轉排序數組中的最小值

已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入數組。例如，原數組 nums = [0,1,2,4,5,6,7] 在變化后可能得到：
若旋轉 4 次，則可以得到 [4,5,6,7,0,1,2]
若旋轉 7 次，則可以得到 [0,1,2,4,5,6,7]
注意，數組 [a[0], a[1], a[2], …, a[n-1]] 旋轉一次 的結果為數組 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
給你一個元素值 互不相同 的數組 nums ，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并返回數組中的 最小元素 。
你必須設計一個時間復雜度為 O(log n) 的算法解決此問題。

比較頭節點或者尾節點

class Solution {
public:int findMin(vector<int>& nums) {int n=nums.size();int left=0;int right=n-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>=nums[0])left=mid+1;elseright=mid;}if(nums[left]>nums[0])return nums[0];return nums[left];}
};

4、LCR 點名

某班級 n 位同學的學號為 0 ~ n-1。點名結果記錄于升序數組 records。假定僅有一位同學缺席，請返回他的學號。

class Solution {
public:///解法：1、哈希表 2、直接變里找結果 3、位運算 4、數學（高斯求和公式）int takeAttendance(vector<int>& records) {int n=records.size();int left=0;int right=n-1;while(left<right){int mid=left+(right-left)/2;if(records[mid]>mid)right=mid;elseleft=mid+1;}if(records[left]==left)return records[n-1]+1;return left;}
};