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)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181116B0BF1K00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券