pyton实现二分查找

pyton实现二分查找

搜索:

pyton实现二分查找

二分查找:

pyton实现二分查找

递归代码:
def binary_search(alist,item):
    """二分查找"""
    low=0
    n=len(alist)
    if n>0:#递归终止条件
        mid=n//2
        if item==alist[mid]:
            return True
        elif item<alist[mid]:
                return binary_search(alist[:mid],item)
        elif item>alist[mid]:
                return binary_search(alist[mid+1:],item)
    else:
        return False
    
    
if __name__=="__main__":
    li=[17,20,26,31,44,54,55,77,93]
    print(binary_search(li,55))
    print(binary_search(li,100))

递归分析:

(1)对于二分查找,针对的是排序好的一个元素。
(2)每次需要进行比较中间元素与所要查找元素的大小
(3)如果要查询的元素比mid处的元素小,辣么就往左边部分继续进行二分查找,即alist[:mid]
(4)如果要查询的元素比mid处的元素大,辣么就往右边部分继续进行二分查找,即alist[mid+1:],继续递归下去
(5)终止条件为n<=0的情况。所以完整代码见上

非递归代码:
def binary_search(alist,item):
    """非递归,二分查找"""
    frist=0
    last=len(alist)-1
    while frist<=last:
        mid=(frist+last)//2
        if item==alist[mid]:
            return True
        elif item<alist[mid]:
            last=mid-1
        else :
            frist=mid+1
    return False

if __name__=="__main__":
    li=[17,20,26,31,44,54,55,77,93]
    print(binary_search(li,55))
    print(binary_search(li,100))

非递归分析:

pyton实现二分查找
(1)首先我们还是和递归一样找到中间元素,也就是mid=(frist+last)//2,就是7.
(2)判断所要查找的元素与mid元素进行比较。
(3)比mid小,就需要更改last,使得last=mid-1
pyton实现二分查找
(4)如果所查元素比mid元素大,则需要更改frist使得frist=mid+1
(5)终止条件是frist<=last

时间复杂度:

pyton实现二分查找
最优复杂度:就是刚好所要查找的元素正好等于mid所指的值。

 

上一篇:阿里云盘列表AList部署教程


下一篇:五、二分法