算法 —— 二分查找
目录
二分查找
在排序数组中查找元素的第一个和最后一个位置
搜索插入位置
x的平方根
山峰数组的峰顶索引
寻找峰值
搜索旋转排序数组中的最⼩值
点名
二分查找模板分为三种：1、朴素的二分模板 2、查找左边界的二分模板 3、查找右边界的二分模板（注意：不是数组有序才使用二分查找，只要存在二段性（一个条件把数组分为两段）都可以使用二分查找）
二分查找
代码如下：
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right){int mid = left + (right - left) / 2;if (nums[mid] > target)right = mid - 1;else if (nums[mid] < target)left = mid + 1;elsereturn mid;}return -1;}
};在排序数组中查找元素的第一个和最后一个位置
这道题可以引出另外两个重要的二分查找模板： 查找左边界的二分模板 查找右边界的二分模板
以上是两个模板的内容，判断条件根据题目内容修改，以题目示例1为例，下面给出具体解释为什么这样做可行：
代码如下：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理为空if (nums.size() == 0)return { -1,-1 };// 找左端点int left_end_point = -1, right_end_point = -1;int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 判断是否有结果if(nums[left]==target)left_end_point = left;// 找右端点 // left可以从左端点开始left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;if (nums[mid] > target)right = mid - 1;elseleft = mid;}if(nums[right] == target)right_end_point = right;if(right_end_point != -1)return { left_end_point,right_end_point };elsereturn { -1,-1 };}
};搜索插入位置
根据 二段性，可以把数组分为小于t和大于等于t两部分，目标索引就是在大于等于的左边界上。
注意示例3的边界情况，代码如下：
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 数组中所有元素小于targetif (nums[left] < target)return left + 1;return right;}
};x的平方根
本题依旧是一个二分查找的算法思想，left为1，right为x本身，根据二段性，将x分为小于等于sqrt（x）的和大于sqrt（x）的，注意小于1的小数和INT_MAX这两个特殊情况， INT_MAX平方后数据太大，要用long long类型来存储。代码如下：
class Solution {
public:int mySqrt(int x) {// 处理边界情况if (x < 1)return 0;int left = 1, right = x;while (left < right){long long mid = left + (right - left + 1) / 2; // 防止溢出if (mid * mid > x)right = mid - 1;elseleft = mid;}return left;}
};山峰数组的峰顶索引
本题依旧是一道二分查找题，数组被分为递增段和递减端两部分，代码如下：
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while (left < right){int mid = left + (right - left + 1) / 2;if (arr[mid] < arr[mid - 1])right = mid - 1;elseleft = mid;}return left;}
};寻找峰值
class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1])left = mid + 1;elseright = mid;}return left;}
};搜索旋转排序数组中的最⼩值
class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1, target = nums[right];while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > target)left = mid + 1;elseright = mid;}return nums[right];}
};
点名
本题可以有多种解法：
此题查找的是左边界，直接写代码即可：
class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (records[mid] == mid)left = mid + 1;elseright = mid;}// 特殊情况0 1 2 3 缺少4return records[left] == left ? left + 1 : left;}
};