我要评论查找
一、线性查找
线性查找法：对于大型列表而言，效率低下。
例：输入一个数字，在一个数字列表中查找，并判断列表中是否存在。如果没有打印提示信息，如果存在打印下标。
代码：
list1 = [55,66,22,11,88,77,99,33,44]
num = eval(input("请输入要查找的数字："))
list1_index = -1 #用来记录查找到的数字下标（用一个不可能的数字为初值，判断时好判断）
#使用循环线性查找
for i in range(len(list1)):
if num == list1[i]:
list1_index = i
break
if list1_index == -1:
print("列表中没有您要查找的数字！")
else:
print("{}的下标为：{}。".format(num,list1_index))
#输入输出样例：
#样例1：
#请输入要查找的数字：22
#22的下标为：2。
#样例2：
#请输入要查找的数字：48
#列表中没有您要查找的数字！
二、二分查找
二分查找法：使用前，将列表升序排列。（如果降序排列，则和下面的规律相反。）
基本原理（规律）：
首先将要查找的元素（key）与列表的中间元素比较
1、如果key小于中间元素，只需要在列表的前一半元素中继续查找key。
2、如果key和中间元素相等，匹配成功。查找结束。
3、如果key大于中间元素，只需要在列表的后一半元素中继续查找key。
实例：随机生成一个有20个元素的列表，输入一个数字查找输入数字的下标。如果没有打印提示信息，如果存在打印下标。
代码：
#二分查找法
import random
list1 = []
#使用循环生成一个元素不重复的列表
for i in range(20):
#rand_num = random.randint(1,101) #1~100之间
#list1.append(rand_num) #生成的随机列表中可能有重复元素
rand_num = random.randint(1,101)
while rand_num in list1: #如果随机数以及在列表中，就重新生成一个
rand_num = random.randint(1,101)
list1.append(rand_num)
#升序排列
list1.sort()
print(list1)
#查找
num = int(input("请输入要查找的数字："))
num_index = -1
low = 0 #最小值（最下边界）的下标
high = len(list1) - 1 #最大值（最大边界）的下标
while high >= low:
mid = (low+high) // 2
#1、如果key小于中间元素，只需要在列表的前一半元素中继续查找key。
#2、如果key和中间元素相等，匹配成功。查找结束。
#3、如果key大于中间元素，只需要在列表的后一半元素中继续查找key。
if num<list1[mid]:
high = mid-1
elif num == list1[mid]:
num_index = mid
break
else:
low = mid + 1
if num_index != -1:
print("要查找的{}元素下标为：{}".format(num,num_index))
else:
print("列表中没有您要查找的元素！")
#输入输出样例：
#样例1：
#[1, 2, 5, 7, 12, 16, 29, 50, 51, 52, 67, 70, 77, 78, 82, 83, 85, 87, 95, 100]
#请输入要查找的数字：29
#要查找的29元素下标为：6
#样例2：
#[6, 12, 21, 27, 28, 32, 43, 46, 50, 51, 52, 54, 58, 65, 73, 75, 78, 91, 93, 97]
#请输入要查找的数字：55
#列表中没有您要查找的元素！
本文地址：https://blog.csdn.net/qq_45856289/article/details/107368643
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论