Python书写实现二分查找返回索引及查找次数

2020-04-11  本文已影响0人  何惧人言
arry1=[i for i in range(1,13)]
arry2=[12   , 15   , 17   , 20  ,  24  ,  30   , 38    ,43,    45,    51,    52]
arry3=[1,2,3,4,5]
def binary_search(num_list, x):
    num_list=sorted(num_list)
    left, right = 0, len(num_list)-1
    count=1
    while left<=right:
        mid =int ((left+right)/2)
        if num_list[mid]>x:
            right=mid-1
            count += 1
        elif num_list[mid]<x:
            left=mid+1
            count += 1
        else:
            return '元素下标为:'+str(mid)+'查找次数为:'+str(count)
    return '不存在'

msg=binary_search(arry1,2)
print(msg)

关于折半查查找的小tip:
1、最差的情况需要查找logN+1关于折半查查找的小tip: 1、最差的情况需要查找logN+1次(logN需向下取整数,底数是2)
2、最优情况下需1次
3、查找某元素需要经过几次折半查询时可以根据该元素在二叉决策树中的位置来判断。例如以下决策树中:查找元素X=5需要查找2次,查找元素X=8需经过查找3次。这种方法简单明了不会被变来变去指针搞得头晕。
4、在查找一个不存在的元素时搜索次数分LogN,即二叉决策树的高度。
码上风云

上一篇 下一篇

猜你喜欢

热点阅读