嗡嘛呢叭咪吽

发布时间：2020-12-14 04:22:37 所属栏目：大数据来源：网络整理

导读：二分查找：一般而言,对于包含n个元素的列表,用二分查找最多需要log2 n(以2为底，n的对数)步,而简单查找最多需要n步。仅当列表是有序的时候,二分查找才管用。函数 binary_search 接受一个有序数组和一个元素。如果指定的元素包含在数组中,这个函数将返回其

二分查找：

一般而言,对于包含n个元素的列表,用二分查找最多需要log2 n(以2为底，n的对数)步,而简单查找最多需要n步。

仅当列表是有序的时候,二分查找才管用。

函数 binary_search 接受一个有序数组和一个元素。如果指定的元素包含在数组中,这个函数将返回其位置。

low = 0? high = len(list) - 1? mid = (low + high) / 2

guess = list[mid]

如果猜的数字小了,就相应地修改 low 。if guess < item: low = mid + 1

如果猜的数字大了,就修改 high 。if guess > item: high = mid - 1

 1 #!coding:utf8
 2 
 3 def binary_search(li,item):
 4     low = 0
 5     high = len(li) -1
 6 
 7     while low <= high:  # 设定有效范围
 8         mid = int((low + high) / 2)  # Python3中需要明确转为整型
 9         guess = li[mid]
10 
11         if guess == item:
12             return mid
13         elif guess > item:
14             high = mid - 1
15         else:
16             low = mid + 1
17     return None
18 
19 my_list = [1,3,5,7,9,11]
20 print(binary_search(my_list,11))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!