【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
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。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^4nums为 无重复元素 的 升序 排列数组-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;
}
};