本文章的所有代码和相关文章， 仅用于经验技术交流分享，禁止将相关技术应用到不正当途径，滥用技术产生的风险与本人无关。 本文章是自己学习的一些记录。
开始
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
示意图
二分查找只能作用到顺序表当中，而且是作用于有序的顺序表当中 按照这样的思路查找元素4是否存在： 根据下标值(红色数字)： 1、首先查找出7为中间值，即(0+8)//2； 2、因为要查找的4小于7，所以在7的左侧查找； 3、在1-6之间查找出中间值为3，即(0+3)//2; 4、因为要查找的4大于3，所以在3的右侧查找； 5、在4-6之间找出中间值为2，即(2+3)//2； 6、所以最终的定位是索引值为2，值为4，存在。 所以这就是二分查找的思路，也可以分为递归的思想和非递归的思想
代码
'''二分查找作用于顺序表，而且是有序的顺序表'''
def binary_search(alist
,item
):
n
=len(alist
)
if n
>0:
mid
= n
// 2
if alist
[mid
]==item
:
return True
elif alist
[mid
]<item
:
return binary_search
(alist
[mid
+1:],item
)
else:
return binary_search
(alist
[:mid
],item
)
return False
'''递归思想是划分后的区域新建立的列表进行调用函数的递归思想
非递归思想是在原有的划分的区域继续进行划分'''
def binary_search_1(alist
,item
):
'''非递归思想的二分查找'''
n
=len(alist
)
first
=0
last
=n
-1
while first
<=last
:
mid
=(first
+last
)//2
if alist
[mid
]==item
:
return True
elif alist
[mid
]<item
:
first
=mid
+1
else:
last
=mid
-1
return False
if __name__
== '__main__':
li
=[17, 20, 26, 31, 44, 54, 55, 77, 93]
print(binary_search
(li
,55))
print(binary_search
(li
,100))
print(binary_search_1
(li
, 77))
print(binary_search_1
(li
, 200))
返回的结果：
时间复杂度的计算
最优时间复杂度： 在计算最优时间复杂度的时候，也就是一开始就找到了要找到的值： 所以最优的时间复杂度为：O(1) 最坏时间复杂度： 因为要查找出想要的元素，也就是不断的二分，在某一个区域进行查找： 所以最坏时间复杂度为：O(logn)
参考资料：传智播客数据结构
