c2c电子商务网站开发,网站建设服务费账务处理,去除wordpress后台登录logo,帝国网站模板下载二分法是一种快速查找的方法#xff0c;时间复杂度低#xff0c;逻辑简单易懂#xff0c;总的来说就是不断的除以2除以2...
但是需要注意#xff1a;待查找的序列区间单调有序
例如需要查找有序数组arr里面的某个关键字key的位置#xff0c;那么首先确认arr的中位数或者中…二分法是一种快速查找的方法时间复杂度低逻辑简单易懂总的来说就是不断的除以2除以2...
但是需要注意待查找的序列区间单调有序
例如需要查找有序数组arr里面的某个关键字key的位置那么首先确认arr的中位数或者中点center下面分为三种情况假如arr[center]key说明key在arr中心左边范围
假如arr[center]
假如arr[center]key说明key在arr中心。
范围每次缩小一半写个while的死循环知道找到为止。
二分法查找非常快且非常常用但是唯一要求是要求数组是有序的
我的另一篇博客刚好介绍了冒泡排序可以去看看http://www.cnblogs.com/TTyb/p/5726151.html
二分法的代码如下1 #!/usr/bin/python3.4
2 # -*- coding: utf-8 -*-
3
4 def BinarySearch(arr, key):
5 # 记录数组的最高位和最低位
6 min 0
7 max len(arr) - 1
8
9 if key in arr:
10 # 建立一个死循环直到找到key
11 while True:
12 # 得到中位数
13 # 这里一定要加int防止列表是偶数的时候出现浮点数据
14 center int((min max) / 2)
15 # key在数组左边
16 if arr[center] key:
17 max center - 1
18 # key在数组右边
19 elif arr[center] key:
20 min center 1
21 # key在数组中间
22 elif arr[center] key:
23 print(str(key) 在数组里面的第 str(center) 个位置)
24 return arr[center]
25 else:
26 print(没有该数字!)
27
28
29 if __name__ __main__:
30 arr [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93]
31 while True:
32 key input(请输入你要查找的数字)
33 if key :
34 print(谢谢使用)
35 break
36 else:
37 BinarySearch(arr, int(key))
运行结果
