Python算法题：二分查找—Testfan打卡学测开1115

本期技术分享讲师Arthur老师

分享内容：

什么是二分查找？

本期语音讲解

本期文字解析

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

算法过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求：

1.必须采用顺序存储结构。

2.必须按关键字大小有序排列。

算法复杂度：

时间复杂度为：O(log2n)

Python代码实现：

def bin_search(data_list, val):

low = 0 # 最小数下标

high = len(data_list) - 1 # 最大数下标

while low

mid = (low + high) // 2 # 中间数下标

if data_list[mid] == val: # 如果中间数下标等于val, 返回

return mid

elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标

high = mid - 1

else: # 如果val在中间数右边, 移动low下标

low = mid + 1

return # val不存在, 返回None

ret = bin_search(list(range(1, 10)), 3)

print(ret)