Python算法设计|二分查找

版权声明：原创不易，本文禁止抄袭、转载，侵权必究！

一、二分查找

二分查找也被称为折半查找，是在一个有序数组中查找特定元素位置的查找算法。二分查找要求查找序列采用顺序存储，且按关键字有序排列

据说，二分查找最先出现在上个世纪50年代，但是直到60年代中期才出现了第一个正确的实现。在2006年，Java 库中关于二分查找的程序仍然因 Bug 的出现不得不被修复。实现一个完美的二分查找是有一定的难度的，要充分考虑到它的退出条件和中间点的计算

二、算法思路

• 从中间元素开始搜索。如果正好是要搜索元素，则搜索结束
• 如果不等，则在大于或者小于要搜索元素的那一半再执行二分查找
• 如果在某一步后要查找的数组为空，则代表找不到，可设为-1

这种算法每一次比较都使搜索范围缩小一半，因此非常高效。

三、Python算法实现

def search(data, item):left, right = 0, len(data) - 1#数组升序while left <= right:middle = (left + right) // 2if item < data[middle]:right = middle - 1elif item > data[middle]:left = middle + 1else:return middle#数组降序# while left >= right:#     middle = (right + left)  // 2#     if item > data[middle]:#         right = middle - 1#     elif item < data[middle]:#         left = middle + 1#     else:#         return middlereturn -1firstSearch = search([3, 5, 8, 10, 15], 0)
print(firstSearch)
secondSearch = search([3, 5, 8, 10, 15], 8)
print(secondSearch)
# secondSearch = search([15,10,8，5,3], 8)
# print(secondSearch)

注意：这里测试的是数组升序以及不存在的情况，如有需要可自行更改相应的情况

四、作者Info

Author：小鸿的摸鱼日常，Goal：让编程更有趣！

专注于算法、爬虫，网站，游戏开发，数据分析、自然语言处理，AI等，期待你的关注，让我们一起成长、一起Coding！

版权说明：本文禁止抄袭、转载 ，侵权必究！