手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

折半查找

时间:2021/5/13 21:39:59|来源:|点击: 次

有10个鸡蛋,有一个坏的(重一些),给你天平。称几次
5 5
2 2
1 1

"""
        0   1  2  3  4  5  6  7  8  9
list = [11,22,33,44,55,66,77,88,99,111]
假设需要:66
第一次:(0 + 9)//2 = 4 ;55 和 66比较,
    接下来在55的右边找:66,77,88,99,111
第二次:(5+9)//2 = 7 88和 66
    接下来在88的左边找:66,77
第三次:(5+6)//2 = 5 66 == 66,对应下标5

开始下标:0开始    慢慢变大
结尾下标:(个数-1) 慢慢减小

"""


list = [11,22,33,44,55,66,77,88,99,111]
n = int(input("输入需要查找的值:"))
start = 0  #最左边开始的下标
end = len(list)-1  ##最右边开始的下标
index = -1  #对应的下标,-1没有找到
while start <= end:
    #中间值 与 n 进行比较
    mid = (start + end) // 2
    if list[mid] == n:  #找到
        index = mid
        break
    elif list[mid] < n:  ##继续 在中间值的右边找
        start = mid + 1
    else:
        end = mid - 1
print("%d对应的下标:%d"%(n,index))

Copyright © 2002-2019 某某自媒体运营 版权所有