做一个美食网站怎么做,广州软件开发培训机构有哪些,phpcmsv9中英文网站,大连建设网中标公司目录 前言
1. 二分查找#xff08;基础版#xff09; 2. 寻找左右端点
循环判断条件
求中间点
总结 前言 说起二分查找#xff0c;也是一种十分常见的算法#xff0c;最常听说的就是#xff1a;二分查找只能在数组有序的场景下使用#xff1b;其实也未必#xff0c;…目录 前言
1. 二分查找基础版 2. 寻找左右端点
循环判断条件
求中间点
总结 前言 说起二分查找也是一种十分常见的算法最常听说的就是二分查找只能在数组有序的场景下使用其实也未必只要能找到规律也依然可以使用本文我将分享一些有关二分查找算法的做题经验 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;
} 在计算中间点时比较推荐示例中的写法
int mid left (right - left) / 2; 这种方式可以有效的防止数据溢出 由此可以总结出基础版本的二分模板
while( left right)
{int mid left (right - left) / 2;if(...) right mid -1;else if(...) left mid 1;else return ...;
} 2. 寻找左右端点 这种方式的二分算法有比较经典的题目
力扣中的第34道题 这种类型再使用基础版本的二分就没法很好的解决
使用基础版本只能找到一组目标值中的某一个比如
nums [5,7,8,8,8,9]; // target 8 基础版本只能保证找到数组中的8目标值但是要知道目标值开始位置和解释位置就不行了还需要进行一些操作但这样就容易让时间复杂度降到 O(N)也就是所有值都是目标值的情况因此基础版本在这道题中并不是最优解这时就可以使用二分的进阶版寻找区间左右端点 怎么找左右端点
还是使用这个示例
nums [5,7,8,8,8,9]; 寻找端点版本主要分成两种情况设中间点为x
以寻找左端点为例以下的示例都是以求左端点
x targetleft mid 1在区间[leftright]中找x targetright mid 将数组划分成两个区间right为什么是等于mid就一目了然了 当mid在如图的位置时如果right mid 1那么剩下的区间就不会有target
较为难的点就是细节的处理这里很容易出错一旦出错就会成死循环
细节求中间点、循环条件
循环判断条件 判断条件是
while(left right){...
} 不需要判断是否相等如果判断了就会死循环
x targetleft mid 1x targetright mid
比如 如果right left时还进入循环判断此时走的是 x targetright还是会在原来的位置这样就会造成死循环
求中间点 求中间点有两种
// 第一种
mid left (right - left) / 2;// 第二种
mid left (right - left 1) / 2;
他们的区别在于当数组元素为偶数的时候
第一种 第二种 求左端点只能使用第一种否则也会造成死循环
如果是第二种情况
假设区间只剩两个端点 使用第二种方法计算出的mid是右边的端点那么当满足 x targetleft mid 1时循环退出如果满足的是 x targetright mid就会出现死循环
而第一种 当满足 x targetleft mid 1时 left走到right位置循环结束
当满足的是 x targetright midright走到mid位置也就是left位置循环结束
总结一下
// 寻找左端点
while(left right) {int mid left (right - left) / 2;if(left target) left mid 1;else right mid;
}// 寻找右端点
while(left right) {int mid left (right - left 1) / 2;if(right target) right mid - 1;else left mid;
} 可以得出模板
// 寻找左端点
while(left right) {int mid left (right - left) / 2;if(...) left mid 1;else right mid;
}// 寻找右端点
while(left right) {int mid left (right - left 1) / 2;if(...) right mid - 1;else left mid;
}
提醒注意本文对二分进行了模板的总结切记不要一味的记忆模板要基于理解去使用
以下是一些题目练习
x的平方根
在排序数组中查找元素的第一个和最后一个位置 山脉数组的峰顶索引 总结 以上便是本文的全部内容希望对你有所帮助最后感谢阅读
