如果有这样一个列表，让你从这个列表中找到66的位置，你要怎么做？
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
方法一：
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
num = input('请输入要查找的数：')
if num.upper() == 'Q':
print('结束查找！')
break
else:
num = int(num)
print('找到了，“{}”的位置是“{}”'.format(num, lst.index(num)))
运行结果：
请输入要查找的数：66
找到了，“66”的位置是“17”
请输入要查找的数：2
找到了，“2”的位置是“0”
请输入要查找的数：88
找到了，“88”的位置是“24”
请输入要查找的数：44
Traceback (most recent call last):
File "D:/Python_Project/Temp.py", line 1872, in <module>
print('找到了，“{}”的位置是“{}”'.format(num, lst.index(num)))
ValueError: 44 is not in list
如上，我们之所以用index方法可以找到，是因为Python帮实现了该查找功能，但index方法找不到时会直接报错，需要另外进行异常处理，并且如果index方法不给我们使用了，还能找到这个66吗？可以通过如下方法二来实现：
方法二：
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
num = input('请输入要查找的数：')
if num.upper() == 'Q':
print('结束查找！')
break
else:
num = int(num)
i = 0
if num in lst:
for n in lst:
if n == num:
print('找到了，“{}”的位置是“{}”'.format(num, i))
i += 1
else:
print('找不到“{}”这个值！'.format(num))
运行结果：
请输入要查找的数：66
找到了，“66”的位置是“17”
请输入要查找的数：2
找到了，“2”的位置是“0”
请输入要查找的数：88
找到了，“88”的位置是“24”
请输入要查找的数：44
找不到“44”这个值！
请输入要查找的数：q
结束查找！
如上方法既可以找到所需要查询的值，也可以处理找不到的值，但现在是怎么找到这个数的呢？是不是循环这个列表，一个一个的找的呀？假如我们这个列表特别长，有好几十万个数，甚至上百万、上千万等，那我们找一个数如果运气不好的话是不是要对比几十万次，甚至上百万、上千万次？这样效率太低了，我们得想一个新办法：二分查找算法。
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
观察下这个列表，这是不是一个从小到大排序的“有序”列表呀？
如果这样，假如我要找的数比列表中间的数还大，是不是我直接在列表的后半边找就行了？
这就是二分查找算法！
那么落实到代码上我们应该怎么实现呢？如下方法三：
方法三：
def find(lst, aim, start = 0 ,end = None):
end = len(lst) if end is None else end
mid_index = (end - start) // 2 + start # 计算中间值
if start > end:
return None
elif lst[mid_index] < aim:
return find(lst, aim, start = mid_index + 1, end = end )
elif lst[mid_index] > aim:
return find(lst, aim, start = start, end = mid_index-1)
else:
return mid_index
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
num = input('请输入要查找的数：')
if num.upper() == 'Q':
print('结束查找！')
break
else:
num = int(num)
ret = find(lst,num)
if ret == None:
print('找不到“{}”这个值！'.format(num))
else:
print('找到了，“{}”的位置是“{}”'.format(num, ret))
运行结果：
请输入要查找的数：66
找到了，“66”的位置是“17”
请输入要查找的数：2
找到了，“2”的位置是“0”
请输入要查找的数：88
找到了，“88”的位置是“24”
请输入要查找的数：44
找不到“44”这个值！
请输入要查找的数：q
结束查找！
网友评论