【算法】二分查找

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

文章目录

引言
一、二分查找
二、查找元素的第一个和最后一个位置
三、x的平方根
四、搜索插入位置
五、山脉数组的峰顶索引
六、寻找峰值
七、寻找旋转数组中的最小值
八、寻找旋转数组中的最小值 ||
总结

引言

二分查找，实际上也是左右双指针的变形，本质是利用数组的二段性进行查找。总共有三个模板：朴素二分、左边界二分、右边界二分

一、二分查找

思路：

这道题就是标准的朴素二分，也是最简单最基础的二分
循环条件：left <= right
求中点（两种方法都可以）：
- int mid = left + (right-left)/2;//求左中点
- int mid = left + (right-left+1)/2;//求右中点
上述求中点方法，可以防止溢出

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) left = mid + 1;else if(nums[mid] > target) right = mid - 1;else return mid;}return -1;}
};

二、查找元素的第一个和最后一个位置

思路：

本题便用到了左边界二分和右边界二分
循环条件：left < right（注意：判断等于会死循环）
左边界二分：int mid = left + (right-left)/2;//求左中点
右边界二分：int mid = left + (right-left+1)/2;//求右中点
出循环后，还要再判断当前位置的值是否为target

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

三、x的平方根

思路：

右边界二分
注意mid*mid数值太大，int 会溢出，所以改成long long

class Solution
{
public:int mySqrt(int x){int left = 1, right = x;while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid <= x) left = mid;else right = mid - 1;}return right;}
};

四、搜索插入位置

思路：

左边界二分

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

五、山脉数组的峰顶索引

思路：

左边界二分（右边界也可以）

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

六、寻找峰值

思路：

左边界二分（右边界也可以）

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]) right = mid;else left = mid + 1;}return left;}
};

七、寻找旋转数组中的最小值

思路：

每次选取right指向的值，作为比较的基准值
左边界二分

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

八、寻找旋转数组中的最小值 ||

思路：

这题是上题的变形，主要改变是存在重复元素
还是左边界二分，不过在 nums[mid] == nums[right] 时，- -right 即可

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