python算法与数据结构-二分查找算法

我会带着你远行 2023-10-06 13:26 25阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70][]

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。

因此折半查找方法适用于不经常变动而查找频繁的有序列表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1][]

递归实现二分查找，代码如下所示:

# coding=utf-8
    #二分查找，递归算法
    def binary_search(alist,item):
        n = len(alist)
        if n>0:
            mid = n//2
            if(alist[mid] == item):
                return True
            elif item < alist[mid]:
                return binary_search(alist[:mid],item)
            else: #这里需要是mid+1，因为mid是中间值上面已经判断了
                return binary_search(alist[mid+1:],item)
        return False
    
    if __name__ == "__main__":
            li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
            print(li)
            res = binary_search(li,26)
            print(res)
            res2 = binary_search(li,88)
            print(res2)
    """
    [17, 20, 26, 31, 44, 54, 55, 77, 93]
    True
    False
    """

非递归实现二分查找，代码如下所示:

# coding=utf-8
    #二分查找，非递归算法
    def binary_search(alist,item):
        """二分查找，非递归"""
        n = len(alist)
        first = 0
        last = n-1
        while first <= last:
            mid = (first+last)//2
            if(alist[mid] == item):
                return True
            elif item < alist[mid]:
                # 这里为什么是last，因为要找的值比中间的值小，列表又是有序的，所以只需要找列表的前面一部分就行，所以last = mid - 1
                last = mid-1
            else:
                # 这里为什么是first，因为要找的值比中间的值大，列表又是有序的，所以只需要找列表的后面一部分就行，所以first = mid+1
                first = mid+1
        return False
    
    if __name__ == "__main__":
            li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
            print(li)
            res = binary_search(li,26)
            print(res)
            res2 = binary_search(li,88)
            print(res2)
            res3 = binary_search(li, 77)
            print(res3)
    """
    [17, 20, 26, 31, 44, 54, 55, 77, 93]
    True
    False
    True
    """

![20200721150253806.png][]

上面的最坏时间复杂度:O(logn)，二分查找又叫折半查找，每次查找都是以2为底取对数，所以最坏时间复杂度:O(logn)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200721145549879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200721150026185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[20200721150253806.png]: https://img-blog.csdnimg.cn/20200721150253806.png