2025寒假备战蓝桥杯01---朴素二分查找的学习
文章目录
- 1.暴力方法的引入
- 2.暴力解法的思考 与改进
- 3.朴素二分查找的引入
- 4.朴素二分查找的流程
- 5.朴素二分查找的细节
- 6.朴素二分查找的题目
1.暴力方法的引入
对于下面的这个有序的数据元素的组合，我们的暴力解法就是挨个进行遍历操作，一直找到和我们的这个target一样的这个元素才终止；
2.暴力解法的思考 与改进
上面的暴力解法试过之后，我们会发现，上面的解法每次只能干掉一个元素，但是如果我们指定某一个元素，比如下面的这个4，这个时候4<5,我们直接往后面看就可以了，前面的全部都被干掉了，这个就是对于上面的暴力解法的这个改进；
3.朴素二分查找的引入
上面可以得知，我们是找一个随机元素，我们的二分查找是取中间的这个元素，但是按照上面的思路，我们可以去任意元素，可以是1/3分段点，或者是1/4分段点，但是只有这个二分查找保留了下来，并没有类似于这个三份，四分之类的；
这个主要是使用数学推导之后就可以发现，当取这个中间元素的时候，我们的这个时间复杂度是最低的；
4.朴素二分查找的流程
下面的这个就是有序数组的这个查找的流程，学过c语言或者数据结构的对于这个应该很熟悉，在此不多言了；
5.朴素二分查找的细节
1）循环的结束：我们的这个left==right的时候，这个还是需要继续进行判断的，直到left>right;
2）根据这个每次取中的原理，可以知道每一次就看到了一半的元素，以此类推求解这个时间复杂度，如图所示；
6.朴素二分查找的题目
1）思路和我们上面的描述就是一致的，不多言了；
2）对于这个mid的取值，本来是可以直接使用这个(left+right)/2计算的，但是这个里面的使用的left+区间长度的一半，这个主要是考虑栈溢出的风险，使用减法巧妙处理掉这个问题；
+区间长度的一半，这个主要是考虑栈溢出的风险，使用减法巧妙处理掉这个问题；
