Java教程

数据结构与算法之二分查找法的总结

本文主要是介绍数据结构与算法之二分查找法的总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二分查找也叫做折半查找。二分查找的条件:①是一个有序序列 ②是一个顺序表。
比如有序的列表:[1,2,3,5,6,7,8,9]

二分查找的复杂度:
最优复杂度:O(1)
最坏复杂度:O(logn)

算法思想:
给定一个序列,查找序列中是否有元素a,查找的方法是:将序列折半,找到中间位置的数值mid,将该数值和a进行比较,比a大,则在左边的序列中找a是否存在,方法还是折半查找,如果mid比a小,那么在中间值右边中的序列中找a是否存在,方法也还是折半查找。可以看到上面有部分重复的功能,就是折半查找,这块可以使用递归,也可以不使用递归。下面会给出两个例子分别介绍这两种方法:

例1:递归实现:

def binary_find(alist,item):
    n = len(alist)
    #递归结束条件
    if n == 0:
        return False
    mid = n//2
    if alist[mid] == item:
        return True
    elif alist[mid] > item:
        return binary_find(alist[:mid],item)
    else:
        return binary_find(alist[mid+1:],item)

l = [1,2,9,34,999]
re = binary_find(l,22)
print(re)
re = binary_find(l,999)
print(re)

运行结果:

False
True

例2:非递归实现

def binary_find2(alist,item):
    n = len(alist)
    start = 0
    end = n-1
    while start <= end:  #这里要注意等于不能少
        mid = (end + start)//2
        if alist[mid] == item:
            return True
        elif alist[mid] > item:
            end = mid - 1
        else:
            start = mid + 1
    return False

l = [1,2,9,34,999]
re = binary_find2(l,22)
print(re)
re = binary_find2(l,999)
print(re)

运行结果:

False
True

复杂度分析:
可以看到上面的最优的复杂度就是正好中间的mid值就是我们要查找的值,复杂度为O(1),最坏复杂度就是:logn

其实如果不用二分法查找,使用for循环也是可以的,但是如果数据很大,那么查找速度很慢,for循环查找的最优复杂度为O(1),最坏复杂度为O(n),而我们的二分法查找最坏复杂度是O(logn),所以可以看到复杂度有所降低。

这篇关于数据结构与算法之二分查找法的总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!