深圳市住房和建设局网站怎么打不开了,wordpress验证,wordpress变成英文,古典网站案例序言#xff1a;
本期#xff0c;我们将要介绍的是有关 二分查找算法 并通过题目帮组大家更好的理解#xff01; 目录
#xff08;一#xff09;基本介绍
1、基本思想
2、解题流程
3、复杂度以及注意事项
#xff08;二#xff09;题目讲解
1、在排序数组中查找…序言
本期我们将要介绍的是有关 二分查找算法 并通过题目帮组大家更好的理解 目录
一基本介绍
1、基本思想
2、解题流程
3、复杂度以及注意事项
二题目讲解
1、在排序数组中查找元素的第⼀个和最后⼀个位置
2、搜索旋转排序数组中的最⼩值
3、搜索二维矩阵
总结 一基本介绍
1、基本思想
二分查找算法Binary Search Algorithm是一种在有序数组中查找目标值的高效算法。它的基本思想是将数组分成两部分然后通过比较目标值和数组的中间元素确定目标值可能存在的位置然后将搜索范围缩小一半逐步逼近目标值的位置直到找到目标值或确定目标值不存在。 2、解题流程
以下是二分查找算法的详细过程
初始化左指针left为数组的起始位置右指针right为数组的末尾位置。计算中间位置的索引midmid left (right - left) /2将目标值与中间位置的元素进行比较 若目标值等于中间位置的元素找到目标值返回中间位置的索引。若目标值小于中间位置的元素说明目标值可能在数组的左半部分将右指针right更新为 mid - 1继续执行步骤 2。若目标值大于中间位置的元素说明目标值可能在数组的右半部分将左指针left更新为 mid 1继续执行步骤 2。重复执行步骤 2 和步骤 3直到找到目标值或确定目标值不存在。即当左指针大于右指针时表示搜索范围为空目标值不存在。 3、复杂度以及注意事项
二分查找算法的时间复杂度为 Olog n其中 n 是数组的大小。由于每次都将搜索范围缩小一半因此算法的效率非常高。
二分查找算法的前提是数组必须是有序的如果数组无序则需要先进行排序操作。此外二分查找算法还可用于在旋转有序数组中查找目标值只需要在比较大小时增加一些额外的判断条件。
需要注意的是二分查找算法适用于静态数组或只读的情况。如果需要频繁地插入或删除元素会导致数组的重新排序影响二分查找的优势。
【小结】
总结起来二分查找算法是一种高效的查找算法适用于有序数组中查找目标值。它的核心思想是通过不断缩小搜索范围以有效地定位目标值。 二题目讲解 接下来我们通过具体的题目带着大家去进行理解相关算法。 1、在排序数组中查找元素的第⼀个和最后⼀个位置 【算法思路】
⽤的还是⼆分思想就是根据数据的性质在某种判断条件下将区间⼀分为⼆然后舍去其中⼀个区间然后再另⼀个区间内查找⽅便叙述⽤ x 表⽰该元素 resLeft 表⽰左边界 resRight 表⽰右边界。 【寻找左边界思路】
寻找左边界 ◦ 我们注意到以左边界划分的两个区间的特点
左边区间 [left, resLeft - 1] 都是⼩于 x 的右边区间包括左边界 [resLeft, right] 都是⼤于等于 x 的
• 因此关于 mid 的落点我们可以分为下⾯两种情况
当我们的 mid 落在 [left, resLeft - 1] 区间的时候也就是 arr[mid] target 。说明 [left, mid] 都是可以舍去的此时更新 left 到 mid 1 的位置继续在 [mid 1, right] 上寻找左边界当 mid 落在 [resLeft right] 的区间的时候也就是 arr[mid] target 。说明 [mid 1, right] 因为 mid 可能是最终结果不能舍去是可以舍去的此时更新 right 到 mid 的位置继续在 [left, mid] 上寻找左边界
• 由此就可以通过⼆分来快速寻找左边界 注意这⾥找中间元素需要向下取整 因为后续移动左右指针的时候 左指针 left mid 1 是会向后移动的因此区间是会缩⼩的右指针 right mid 可能会原地踏步⽐如如果向上取整的话如果剩下 1,2 两个元素 left 1 right 2 mid 2 。更新区间之后 leftrightmid 的值没有改变就会陷⼊死循环 因此⼀定要注意当 right mid 的时候要向下取整。 【寻找右边界思路】
寻右左边界◦ ⽤ resRight 表⽰右边界◦ 我们注意到右边界的特点
左边区间包括右边界 [left, resRight] 都是⼩于等于 x 的右边区间 [resRight 1, right] 都是⼤于 x 的
• 因此关于 mid 的落点我们可以分为下⾯两种情况
当我们的 mid 落在 [left, resRight] 区间的时候说明 [left, mid - 1] mid 不可以舍去因为有可能是最终结果都是可以舍去的此时更新 left 到 mid 的位置 当 mid 落在 [resRight 1, right] 的区间的时候说明 [mid, right] 内的元素是可以舍去的此时更新 right 到 mid - 1 的位置
• 由此就可以通过⼆分来快速寻找右边界 注意这⾥找中间元素需要向上取整 因为后续移动左右指针的时候 左指针 left mid 可能会原地踏步⽐如如果向下取整的话如果剩下 1,2 两个元素 left 1 right 2mid 1 。更新区间之后 leftrightmid 的值没有改变就会陷⼊死循环。右指针 right mid - 1 是会向前移动的因此区间是会缩⼩的 因此⼀定要注意当 right mid 的时候要向下取整。 【代码展示】
class Solution {
public:vectorint searchRange(vectorint nums, int target) {// 处理边界情况if(nums.size() 0) return {-1, -1}; //创建一个变量来记录结果的左端点int begin 0;// 1. ⼆分左端点int left 0;int 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};}
};
【解释说明】 在边界情况下如果给定的数组为空则直接返回结果为{-1, -1}。 创建一个变量来记录结果的左端点。begin 初始化左右指针和分别指向数组的起始位置和末尾位置。left right 第一个while循环是为了找到目标值的左端点使用二分查找的思想。 将中间位置的索引计算为这是一个向下取整的操作。mid (left right) / 2如果中间位置的元素小于目标值说明目标值可能在右半部分将左指针更新否则目标值可能在左半部分或者当前位置为目标值的左端点将右指针更新为。right mid重复上述操作直到和指针相等时退出循环。left right 判断是否等于目标值如果不等于则说明目标值不存在于数组中返回结果为{-1, -1}。nums[left] target 否则标记左端点位置为。begin left 第二个while循环是为了找到目标值的右端点同样使用二分查找的思想。 将中间位置的索引计算为这个是为了取整到右边的元素。mid (left right 1) / 2如果中间位置的元素小于等于目标值说明目标值可能在右半部分或者当前位置为目标值的右端点将左指针更新否则目标值可能在左半部分将右指针更新为。right mid - 1重复上述操作直到和指针相等时退出循环。left right 返回结果为{, }即目标值的范围。
【性能分析】 这段代码可以在时间复杂度为Olog n的时间内找到有序数组中目标值的范围其中n是数组的大小两次二分查找分别找到目标值的左右端点从而确定目标值在数组中的范围。 2、搜索旋转排序数组中的最⼩值 【算法思路】
题⽬中的数组规则如下图所⽰ 其中 C 点就是我们要求的点。⼆分的本质找到⼀个判断标准使得查找区间能够⼀分为⼆。 通过图像我们可以发现 [AB] 区间内的点都是严格⼤于 D 点的值的 C 点的值是严格⼩ 于 D 点的值的。但是当 [CD] 区间只有⼀个元素的时候 C 点的值是可能等于 D 点的值。因此初始化左右两个指针 left right 然后根据 mid 的落点我们可以这样划分下⼀次查询的区间
当 mid 在 [AB] 区间的时候也就是 mid 位置的值严格⼤于 D 点的值下⼀次查询区间在 [mid 1right] 上当 mid 在 [CD] 区间的时候也就是 mid 位置的值严格⼩于等于 D 点的值下次查询区间在 [leftmid] 上。
当区间⻓度变成 1 的时候就是我们要找的结果
【代码展示】
class Solution {
public:int findMin(vectorint nums) {int left 0;int right nums.size() - 1;int x nums[right]; // 标记⼀下最后⼀个位置的值while(left right){int mid left (right - left) / 2;if(nums[mid] x) left mid 1;else right mid;}return nums[left];}
};
【解释说明】 初始化左右指针和分别指向数组的起始位置和末尾位置。leftright 创建一个变量来存储数组最后一个位置上的值即数组中的最大值。这是为了标记最后一个位置的值以便在最后返回最小值。xnums[right] 进入while循环判断条件是即左指针小于右指针时执行循环。left right 将中间位置的索引计算为这是一个向下取整的操作。mid(left right) / 2 比较中间位置的元素和最后一个位置的值。nums[mid]x 如果说明最小值在mid的右侧将左指针更新否则最小值可能在mid的左侧或者就是当前位置mid将右指针更新为。重复上述操作直到和指针相等时退出循环。 循环结束后返回即找到的最小值。nums[left] 【性能分析】
时间复杂度为Olog n的时间内找到旋转排序数组的最小值其中n是数组的大小通过二分查找的方式逐渐缩小查找范围最终找到最小值的位置。 3、搜索二维矩阵 【算法思路】
1、初始化两个指针一个指针指向二维矩阵的左上角即第一行第一列的元素另一个指针指向二维矩阵的右下角即最后一行最后一列的元素。利用这两个指针来缩小搜索范围。
2、在每次循环中首先比较左上角指针所指的元素与目标值的关系
如果左上角指针所指的元素等于目标值说明找到目标值返回true。如果左上角指针所指的元素大于目标值说明目标值可能在左上角指针所在的列的左侧将右下角指针的列数减1。如果左上角指针所指的元素小于目标值说明目标值可能在左上角指针所在的行的下方将左上角指针的行数加1。
3、重复步骤5直到左上角指针的行数大于右下角指针的行数或者左上角指针的列数大于右下角指针的列数表示搜索范围已经缩小到无法再继续缩小的情况
【代码实现】
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {if (matrix.empty() || matrix[0].empty()) {return false;}int m matrix.size();int n matrix[0].size();int left 0;int right m * n - 1;while (left right) {int mid left (right - left) / 2;int row mid / n;int col mid % n;if (matrix[row][col] target) {return true;} else if (matrix[row][col] target) {left mid 1;} else {right mid - 1;}}return false;}
};
【解释说明】 首先检查矩阵是否为空如果是空矩阵则直接返回。 获取矩阵的行数和列数。 初始化左指针为0右指针为矩阵总元素数减1。 进入while循环判断条件是即左指针小于等于右指针时执行循环。left right 计算中间位置的索引使用进行计算。mid(left right) / 2 根据中间索引计算出对应的行和列通过和分别得到行和列的值。 将矩阵中对应的元素与目标值进行比较。 如果等于则找到目标值返回。如果小于说明目标值可能在当前位置的右侧将左指针更新。如果大于说明目标值可能在当前位置的左侧将右指针更新。重复上述操作直到找到目标值或者左指针大于右指针时退出循环。 循环结束后如果没有找到目标值返回。
【性能分析】
该算法的时间复杂度为Omn其中m为二维矩阵的行数n为二维矩阵的列数。算法利用了二维矩阵的特点在每次比较后可以减少一行或一列的搜索范围从而快速找到目标值或确定不存在目标值。 总结
请⼤家⼀定不要觉得背下模板就能解决所有⼆分问题。⼆分问题最重要的就是要分析题意然后确定要搜索的区间根据分析问题来写出⼆分查找算法的代码。
要分析题意确定搜索区间不要死记模板不要看左闭右开什么乱七⼋糟的题解要分析题意确定搜索区间不要死记模板不要看左闭右开什么乱七⼋糟的题解要分析题意确定搜索区间不要死记模板不要看左闭右开什么乱七⼋糟的题解
重要的事情说三遍。
【模板记忆技巧】
1. 关于什么时候⽤三段式还是⼆段式中的某⼀个⼀定不要强⾏去⽤⽽是通过具体的问题分析情况根据查找区间的变化确定指针的转移过程从⽽选择⼀个模板。2. 当选择两段式的模板时 在求 mid 的时候只有 right - 1 的情况下才会向上取整也就是 1 取中间数 以上便是关于 二分查找 算法的全部知识讲解大家多加练习立即这部分算法还是很轻松的
