二分法详解
前言
寒假太无无聊,看了点算法,本次写算法入门中最简单的二分法查找,二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法
算法优点
1.计算简单,方法可靠
2.二分法计算过程简单,程序容易实现
3.二分查找每一次判断即可筛选掉一半数据, 效率比全遍历的线性查找的确高很多,
算法缺点
1.只对有序数据有效
2.只能返回一个值
代码展示与解释
def lgfind(arr, v): |
主体方法如上
代码其实很好懂,涉及到的数学知识很简单,主要是在比较时,你要知道怎么去实现折半的操作.
如果认为自己搞不清楚折半是怎么进行实现的,可以在上面的代码中加入两行print语句去看看在查找过程中,那个中位数数值和索引的变化,加入print语句的代码如下:
def lgfind(arr, v): |
这里我们可以传入一个简单数组进行验证
mylist = [1,3,5,7,9] |
这里我们随便传入了一个简单的列表而且是有序的
我们可以运行一下程序,看看结果
从运行结果我们就能直观的认识到,二分法是怎么运行的
我们的lgfind函数,会先将传入的数据进行排序,之后去获取中位数的索引,使用索引去获取当前中位数的具体数值.
当第一次比较不成功后,进入下一个if语句,把当前中位数数值与需要查找的数据的数值进行比较,如果当前中位数大于所传入的数值,也就说明了查找的数值在传入数据的前半段,则在当前中位数索引数值-1(mid-1)的情况下,作为第二次判断时的high这个参数,也就是第二次判断中最大的数值,来达到在数据前半段查找的结果.
如果当前中位数小于所查找的数值,则说明了查找的数值在数据的后半段,这时在当前中位数索引+1(mid+1)的情况下,作为第二次判断的start这个参数,也就是第二次判断中的最小值,来达到在数据后半段查找的结果
而二分法查找的时间复杂度O(logn)。
本次二分法解释就到这里了.感谢大家的阅读,在这特殊时期祝大家身体健康.
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 逆光海!