建立网站内容,wordpress是什么东西,在线设计公司logo,智能网站建设服务Ciallo#xff5e;(∠・ω )⌒☆ ~ 今天#xff0c;塞尔达将和大家一起做几道二分查找算法算法题 ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页#xff1a;椎名澄嵐-CSDN博客 算法专栏#xff1a;★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客…Ciallo(∠・ω )⌒☆ ~ 今天塞尔达将和大家一起做几道二分查找算法算法题 ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页椎名澄嵐-CSDN博客 算法专栏★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客 ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 目录
壹 力扣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(vectorint 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:vectorint searchRange(vectorint 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(vectorint 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(vectorint 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(vectorint 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(vectorint 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(vectorint 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;}
}; ~ 完 ~
