深入解析二分查找法之基础篇

BlaXuan · 发表于 2022-2-20 08:35

#算法篇

我们的女朋友都读得懂系列开新专栏啦，就是我们的算法专栏！！！
新专栏新学习宗旨，算法专栏呢也有一条我们学习算法路上的重要原则。
学习任何知识，我们都要尝试去寻找这个知识最底层的逻辑，哪怕一时间寻找不出来，我们也要在挖掘这最底层的过程中，一步步总结，我们要做知识的明白人。会和明白是有距离的。

记住算法逻辑就两个点：
1. 解决问题，先把问题解决了
2. 优化，优化什么？把没必要做的操作删除掉
第一节呢，小伙伴们要学习一个相对比较好理解的算法。

#二分查找法基础篇（）

1. 1，2，3，4，5，6？里面有5吗？
a) 让计算机解决这个问题？
伪代码：
int[] nums = 1,2,3,4,5,6 ;
for num nums{
if(num == 5) return true;
}
上述伪代码的逻辑就是，遍历数组，查找目标值。
设数组长度为n,那么该算法的时间复杂度为O(n)。
OK啦！很好，问题就解决啦

2. 优化思想？？？
重复一遍优化算法的原则：删除不必要的操作
观察发现，数组元素可比且数组有序。
思考，有必要把数组里的每个元素都遍历一遍吗？？？
进一步讲假设我们先比较nums[3] = 4  <  5,我们还用遍历nums[0]、nums[1]、nums[2]吗？？？
3. 二分查找法？
二分查找法思想：
比较数组中间元素，通过判断，来决定舍弃数组前半部分还是后半部分。此时，算法的时间复杂度为O(logn)
伪代码：
int[] nums = 1,2,3,4,5,6 ;
int target = 5;
int length = nums.length;
int l = length - 1;//左索引
int r = 0;
while (l > r){//结束条件
int mid = (l + r) / 2; //中间索引
if (nums[mid] == target){
      return true;//找到目标元素
}
if (target > nums[mid]){//比中间数大，则舍弃前半段
      l = mid + 1;
}else {//比中间数小
      r = mid - 1;//比中间数小，则舍弃后半段
}
}
return false;//没找到
#二分查找基础例题
给算法真刀真枪的干一场吧！！！
例题：leetcode34 ！！！
最重要的事情，例题可以不会做，但是看完答案你要体会上面讲的二分查找法的思想所在！！！
如果这条没做到，那就违背了我们学习的初衷，学一个小时，我们就会一个小时的东西！

好啦，我们算法之二分查找法基础篇就先到这啦，真的为女朋友都读得懂系列。
下一节呢，就为二分查找法进阶篇，干货多多，贼有意思！！！

		自动登录	找回密码
密码			立即注册