Python 之查找（线性查找和二分查找）

查找

一、线性查找

线性查找法：对于大型列表而言，效率低下。

例：输入一个数字，在一个数字列表中查找，并判断列表中是否存在。如果没有打印提示信息，如果存在打印下标。

代码：

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
#列表中没有您要查找的元素！