【704】二分查找（模板題）看到復雜度logN，得想到二分

給定一個?n?個元素有序的（升序）整型數組?nums?和一個目標值?target??，寫一個函數搜索?nums?中的?target，如果目標值存在返回下標，否則返回?-1。
示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4

示例?2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假設?nums?中的所有元素是不重復的。
2. n?將在?[1, 10000]之間。
3. nums?的每個元素都將在?[-9999, 9999]之間。

?可作為二分查找模板

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1; // 對撞指針while(left <= right){int mid = (right - left) / 2 + left;if(nums[mid] > target) right = mid - 1;else if(nums[mid] < target) left = mid + 1;else return mid;  }return -1;}
};

【35】搜索插入位置

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為?O(log n)?的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums?為?無重復元素?的?升序?排列數組
• -10^4 <= target <= 10^4

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

【162】尋找峰值

峰值元素是指其值嚴格大于左右相鄰值的元素。

給你一個整數數組?nums，找到峰值元素并返回其索引。數組可能包含多個峰值，在這種情況下，返回?任何一個峰值?所在位置即可。

你可以假設?nums[-1] = nums[n] = -∞?。

你必須實現時間復雜度為?O(log n)?的算法來解決此問題。

示例 1：

輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函數應該返回其索引 2。

示例?2：

輸入：nums = [1,2,1,3,5,6,4]
輸出：1 或 5 
解釋：你的函數可以返回索引 1，其峰值元素為 2；或者返回索引 5， 其峰值元素為 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 對于所有有效的?i?都有?nums[i] != nums[i + 1]

思路一：排序，找最大值

思路二：二分取中間值，若中間值的左鄰大，則峰值一定在左邊；若中間值的右鄰大，峰值一定在右邊。?

class Solution {
public:int findPeakElement(vector<int>& nums) {int l = 0, r = nums.size() - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] < nums[mid+1]) l = mid + 1;else r = mid;}return l;}
};

?【74】搜索二維矩陣

給你一個滿足下述兩條屬性的?m x n?整數矩陣：

• 每行中的整數從左到右按非嚴格遞增順序排列。
• 每行的第一個整數大于前一行的最后一個整數。

給你一個整數?target?，如果?target?在矩陣中，返回?true?；否則，返回?false?。

?

?思路一、一次二分查找，將二維矩陣的元素進行查找

思路二、用二分查找找目標元素所在行，再用一次二分查找去找所作行的目標元素。如下：

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {// 1.先找目標數在第幾行int left = 0, right = matrix.size() - 1;while(left <= right){int mid = (left + right) / 2;if(matrix[mid][0] > target) right = mid - 1;else if(matrix[mid][0] < target) left = mid + 1;else return true;}int row = left - 1; // 得到目標行cout << row;if(row < 0) return false;// 2.對目標行進行二分查找left = 0;right = matrix[row].size() - 1;while(left <= right){int mid = (left + right) / 2;if(matrix[row][mid] > target) right = mid - 1;else if(matrix[row][mid] < target) left = mid + 1;else return true;}return false;}
};