★ 算法 OJ 问题 ★ 二分查找算法
Ciallo～(∠・ω< )⌒☆ ~ 今天，塞尔达将和大家一起做几道二分查找算法算法题 ~
❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️
澄岚主页：椎名澄嵐-****博客
算法专栏：★ 优选算法100天 ★_椎名澄嵐的博客-****博客
❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️
目录
壹 力扣704 - 二分查找
1.1 题目
1.2 算法解析
1.3 撰写代码
1.4 朴素二分查找模板
贰 力扣34 - 在排序数组中查找元素的第⼀个和最后⼀个位置
2.1 题目
2.2 算法解析
2.3 撰写代码
2.4 二分查找模板
叁 力扣35 - 搜索插入位置
3.1 题目
3.2 算法解析
3.3 撰写代码
肆 力扣69 - x的平方根
4.1 题目
4.2 算法解析
4.3 撰写代码
伍 力扣852 - 山峰数组的峰顶索引
5.1 题目
5.2 算法解析
5.3 撰写代码
陆 力扣162 - 寻找峰值
6.1 题目
6.2 算法解析
6.3 撰写代码
柒 力扣153 - 寻找旋转排序数组中的最小值
7.1 题目
7.2 算法解析
7.3 撰写代码
捌 力扣LCR173 - 点名
8.1 题目
8.2 算法解析
8.3 撰写代码
~ 完 ~
壹 力扣704 - 二分查找
1.1 题目
704. 二分查找 - 力扣（LeetCode）
1.2 算法解析
首先想到的暴力解法就是遍历数组，找到target，时间复杂度为O(N)，那么有没有更快速的方法呢~
二分查找算法适用于有二段性的区间，比如一个值的左边比这个值小，右边比此值大，根据数学期望，中间值为最佳~
1.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;
else return mid;
}
return -1;
}
};
1.4 朴素二分查找模板
while(left <= right)
{
int mid = left + (right - left) / 2;
if (......)
right = mid - 1;
else if (......)
left = mid + 1;
else
return ......;
}贰 力扣34 - 在排序数组中查找元素的第⼀个和最后⼀个位置
2.1 题目
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
2.2 算法解析
2.3 撰写代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 处理数组为空
if(nums.size() == 0) return {-1, -1};
// 1. 二分左端点
int begin = 0;
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid;
}
// 判断是否有结果
if(nums[left] != target) return {-1, -1};
else begin = left; // 记录结果
// 2. 二分右端点
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;
}
// 左端点有结果右端点一定有结果
return {begin, right};
}
};
2.4 二分查找模板
1. 二分左端点模板
while(left < right)
{
int mid = left + (right - left) / 2;
if(......) left = mid + 1;
else right = mid;
}2. 二分右端点模板
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(......) left = mid;
else right = mid - 1;
}叁 力扣35 - 搜索插入位置
3.1 题目
35. 搜索插入位置 - 力扣（LeetCode）
3.2 算法解析
3.3 撰写代码
class Solution {
public:
int searchInsert(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 right = mid;
}
if (nums[left] < target) return left + 1;
else return left;
}
};
肆 力扣69 - x的平方根
4.1 题目
69. x 的平方根 - 力扣（LeetCode）
4.2 算法解析
此题需要考虑边界情况， <1单独处理~
并且数据过大有溢出风险，要用long long来存~
4.3 撰写代码
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) left = mid;
else right = mid - 1;
}
return left;
}
};
伍 力扣852 - 山峰数组的峰顶索引
5.1 题目
852. 山脉数组的峰顶索引 - 力扣（LeetCode）
5.2 算法解析
5.3 撰写代码
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]) left = mid;
else right = mid - 1;
}
return left;
}
};
陆 力扣162 - 寻找峰值
6.1 题目
162. 寻找峰值 - 力扣（LeetCode）
6.2 算法解析
无序数组有二段性时也可以使用二分查找算法~
6.3 撰写代码
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;
}
};
柒 力扣153 - 寻找旋转排序数组中的最小值
7.1 题目
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
7.2 算法解析
7.3 撰写代码
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int n = nums[right];
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > n) left = mid + 1;
else right = mid;
}
return nums[left];
}
};
捌 力扣LCR173 - 点名
8.1 题目
LCR 173. 点名 - 力扣（LeetCode）
8.2 算法解析
8.3 撰写代码
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;
else right = mid;
}
if(records[left] == left) return left + 1;
else return left;
}
};
