电子商务网站建设的目的和作用,十大装饰公司排名,外贸网站建设工作计划,装修网站模板下载#x1f387;个人主页#xff1a;Ice_Sugar_7 #x1f387;所属专栏#xff1a;算法详解 #x1f387;欢迎点赞收藏加关注哦#xff01; 二分查找算法简介
这个算法的特点就是#xff1a;细节多#xff0c;出错率高#xff0c;很容易就写成死循环有模板#xff0c;但… 个人主页Ice_Sugar_7 所属专栏算法详解 欢迎点赞收藏加关注哦 二分查找算法简介
这个算法的特点就是细节多出错率高很容易就写成死循环有模板但切记要在理解的基础上记忆不要死记硬背。有三个模板一个是本文要讲的简单模板另外两个分别是查找左、右边界的模板会在后面的文章中讲解
正文
时间复杂度的推导过程
啥时候用二分算法
能找到某种规律根据这个规律能找到某个点以这个点能把区间划分为两块其中一半区间可以舍弃掉只需从另一半区间中继续查找
这么说肯定会觉得抽象没事儿后面做题慢慢体会 不过现在需要知道不一定要数据有序才能用二分查找只要能以某个点将区间分成两段就可以了简称为“二段性”
细节
循环结束的条件
一开始定义两个指针 left 和 right 分别指向数组的起始位置和最后一个位置在每次循环中我们只比较区间中点值 mid 和目标值 target 的大小关系只知道这两个值区间中剩下的值是啥仍然未知即使这个区间只剩下一个数也还是不知道它是谁此时需要拿它和 target 作比较
所以当 left right 时循环才结束
找区间的中点
由数学知识可得 mid left right/ 2 但是如果 left 和 right 很大的话很可能会溢出所以比较稳妥的写法是 mid left right - left/ 2即左端点加上区间长度的一半
如果一共有奇数个元素那么 mid 就是正中间那个如果有偶数个那就有两个中点上面那两个式子算出来的是靠左边的中点
而如果要找靠右边的中点只需加个1mid left right 1/ 2 和 mid left right - left 1/ 2 简单的二分查找模板
来道简单题它的答案就是模板 二分查找
class Solution {public int search(int[] nums, int target) {int left 0,right nums.length-1;while(left right) {int mid left(right-left)/2;if(nums[mid] target) left mid1;else if(nums[mid] target) right mid - 1;else return mid;}return -1;}
}模板为
public int search(int[] nums, int target) {int left 0,right nums.length-1;while(left right) {int mid left(right-left)/2;if(...) left mid1;else if(...) right mid - 1;else return ...;}return -1;}使用时把省略号处的内容填充上就ok了
