二分法详解

前言

寒假太无无聊,看了点算法,本次写算法入门中最简单的二分法查找,二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法

算法优点

1.计算简单，方法可靠

2.二分法计算过程简单,程序容易实现

3.二分查找每一次判断即可筛选掉一半数据, 效率比全遍历的线性查找的确高很多,

算法缺点

1.只对有序数据有效

2.只能返回一个值

代码展示与解释

def lgfind(arr, v):
    arr = sorted(arr)  # 排序数组，从小到大
    print(arr)
    start = 0  # 变量开始
    arrLen = len(arr) - 1  # 变量结束
    while start<=arrLen:
        mid=(start+arrLen)//2
        guess=mylist[mid]
        if guess==v: 
            return mid# 如果中间的找到直接返回
        if guess>v:
            arrLen=mid-1  # 结果在前半段
        else:
            start=mid+1 # 结果在后半段
    return None    # 没有则返回假

主体方法如上

代码其实很好懂,涉及到的数学知识很简单,主要是在比较时,你要知道怎么去实现折半的操作.

如果认为自己搞不清楚折半是怎么进行实现的,可以在上面的代码中加入两行print语句去看看在查找过程中,那个中位数数值和索引的变化,加入print语句的代码如下:

def lgfind(arr, v):
    arr = sorted(arr)  # 排序数组，从小到大
    print(arr)
    start = 0  # 变量开始
    high = len(arr) - 1  # 变量结束
    while start<=high:
        mid=(start+high)//2
        print("这是中位数的位置索引",mid)
        guess=mylist[mid]
        print("这是中位数",guess)
        if guess==v: 
            return mid# 如果中间的找到直接返回
        if guess>v:
            high=mid-1  # 结果在前半段
        else:
            start=mid+1 # 结果在后半段
    return None    # 没有则返回假

这里我们可以传入一个简单数组进行验证

mylist = [1,3,5,7,9]
print(lgfind(mylist, 3))#输出所查找数字的索引

这里我们随便传入了一个简单的列表而且是有序的

我们可以运行一下程序,看看结果

从运行结果我们就能直观的认识到,二分法是怎么运行的

我们的lgfind函数,会先将传入的数据进行排序,之后去获取中位数的索引,使用索引去获取当前中位数的具体数值.

当第一次比较不成功后,进入下一个if语句,把当前中位数数值与需要查找的数据的数值进行比较,如果当前中位数大于所传入的数值,也就说明了查找的数值在传入数据的前半段,则在当前中位数索引数值-1(mid-1)的情况下,作为第二次判断时的high这个参数,也就是第二次判断中最大的数值,来达到在数据前半段查找的结果.

如果当前中位数小于所查找的数值,则说明了查找的数值在数据的后半段,这时在当前中位数索引+1(mid+1)的情况下,作为第二次判断的start这个参数,也就是第二次判断中的最小值,来达到在数据后半段查找的结果

而二分法查找的时间复杂度O(logn)。

本次二分法解释就到这里了.感谢大家的阅读,在这特殊时期祝大家身体健康.