Python中最简单的查找方法
in运算符是python中最简单的查找方法。
>>> 15 in [3,5,2,4,1]
False
>>> 3 in [3,5,2,4,1]
True
这种方法简单而且高效。但为了加深对查找算法的理解，我们还会尝试用python实现一些简单查找算法的逻辑。
顺序查找
顺序查找是一种非常简答的查找方式。从第一个项开始，逐一遍历整个列表，直到找到需要找的元素。当遍历完整个列表仍然没有找到时，则说明需要查找的元素并不在列表中。
# 顺序查找
# items_list为元素列表，item为需要查找的元素
# 查找到时返回True，没有找到时则返回False
def sequentialSearch(items_list, item):
index = 0
while index<len(items_list): #逐个遍历
if item == items_list[index]: #找到元素，返回True
return True
index += 1
return False #遍历结束依然没能找到，则返回False
def main():
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print('-----------------')
print(sequentialSearch(testlist, 13))
print('-----------------')
print(sequentialSearch(testlist, 0))
if __name__ == "__main__":
main()
运行结果为：
False
-----------------
True
-----------------
True
无序列表顺序查找的时间复杂度为O(n)。
当列表不包含所查元素时，有序列表可以比无序列表更早的停止遍历，但时间复杂度也依然是O(n)。
二分查找
二分查找是一种针对有序数列的查找方式。
二分查找从中间项开始，而不是按顺序查找列表。 如果该项是我们正在寻找的项，我们就完成了查找。 如果它不是，我们可以使用列表的有序性质来消除剩余项的一半。如果我们正在查找的项大于中间项，就可以消除中间项以及比中间项小的一半元素。如果该项在列表中，肯定在大的那半部分。
这里，我们暂时不考虑排序的问题，只实现二分查找本身：
# 二分查找
# items_list为升序排序后的元素列表，item为需要查找的元素
# 查找到时返回True，没有找到时则返回False
def binaryChop(items_list, item):
leftpos = 0
rightpos = len(items_list)-1
while leftpos<=rightpos :
midpos = (leftpos+rightpos)//2 #中点位置
if items_list[midpos] == item: #找到元素
return True
elif items_list[midpos] < item: #元素可能在比中点更大的一侧
leftpos = midpos+1
else: #元素可能在比中点更小的一侧
rightpos = midpos-1
return False #没能找到，则返回False
def main():
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binaryChop(testlist, 3))
print('-----------------')
print(binaryChop(testlist, 13))
print('-----------------')
print(binaryChop(testlist, 0))
if __name__ == "__main__":
main()
运行结果如下：
False
-----------------
True
-----------------
True
我们也可以采用递归的写法来书写这段代码，让程序的逻辑更加清晰：
# 二分查找2
# items_list为升序排序后的元素列表，item为需要查找的元素
# 查找到时返回True，没有找到时则返回False
def binaryChop_2(items_list, item):
if 0 == len(items_list): #待查列表已经为空
return False
midpos = (len(items_list)-1)//2 #中点
if items_list[midpos] == item: #找到元素
return True
elif items_list[midpos] < item: #元素可能在比中点更大的一侧
return binaryChop_2(items_list[midpos+1:], item)
else: #元素可能在比中点更小的一侧
return binaryChop_2(items_list[:midpos], item)
def main():
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binaryChop_2(testlist, 3))
print('-----------------')
print(binaryChop_2(testlist, 13))
print('-----------------')
print(binaryChop_2(testlist, 0))
if __name__ == "__main__":
main()
运行结果依然是：
False
-----------------
True
-----------------
True
二分查找的时间复杂度为O(logn)要低于顺序查找的时间复杂度。但考虑到二分查找需要进行排序，因而二分查找并不一定在任何场合都好于顺序查找。如果在小数据上进行单次查找，那么直接使用顺序查找是更为适合的。如果在大数据上需要进行多次频繁的查找，那么排序的时间成本就可以被分摊得很低，这种场景最适合使用二分查找。
