[Python知识库]Python——组合数据类型的应用_2.二分查找

二分查找是一种效率比较高的查找方法。但二分查找要求原始数据是有序的,程序首先使用列表的 sort()方法对数据进行排序,然后再进行查找。

二分查找的基本思想是将要查找的数值 find 与中间位置的数据进行比较,若相等,查找结束。否则,将 find 值与中间数据进行比较,如果小于中间数据,则继续在左边的数据区重复二分查找;如果大于中间数据,则继续在右边的数据区重复二分查找。二分查找需要比较的次数为log?n。

程序中通过一个标记 flag 能表示查找是否成功,如果成功,则跳出 while 循环。

例 5-18 使用二分查找的Python程序 :

#ex0518.py
list1 = [1,42,3,-7,8,9,-10,5]
#二分查找要求查找的序列是有序的,假设是升序列表
list1.sort()
print(list1)

find = eval(input("请输入要查看的数据："))

low = 0
high = len(list1)-1
flag = False
while low <= high:
    mid = int((low + high)/2)

    if list1[mid] == find:
        flag = True
        break
    #左半边
    elif list1[mid] > find:
        high = mid - 1
    #右半边
    else:
        low = mid + 1

if flag == True:
    print("您查找的数据{}，是第{}个元素".format(find,mid+1))
else:
    print("没有您要查找的数据")