Python 算法之二分查找

Python 算法之二分查找

二分查找

• 二分查找又称折半查找
• 优点是比较次数少，查找速度快，平均性能好
• 缺点是要求待查表为有序表，且插入删除困难
• 折半查找方法适用于不经常变动而查找频繁的有序列表。

猜数字游戏

• 1、生成一个有序列表
• 2、用户猜测某个数字是否在列表中　

代码

#!/usr/bin/env python
 
def binary_search(data_source, find_n):
    mid = int(len(data_source)/2)
    if mid >= 1:
        if data_source[mid] > find_n: # data in left
            print("data in left of [%s]" % data_source[mid])
            print(data_source[:mid])
            binary_search(data_source[:mid], find_n)
        elif data_source[mid] < find_n: # data in right
            print("data in right of [%s]" % data_source[mid])
            print(data_source[mid:])
            binary_search(data_source[mid:], find_n)
        elif data_source[mid] == find_n:
            print("found %s" % data_source[mid])
    elif data_source[mid] == find_n:
        print("found %s" % data_source[mid])
    else:
        print("not found")


if __name__ == '__main__':
    data = list(range(1,100,3))
    ret = input("请输入猜测的数字：")
    binary_search(data, int(ret))

运行结果

请输入猜测的数字：50
data in right of [49]
[49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97]
data in left of [73]
[49, 52, 55, 58, 61, 64, 67, 70]
data in left of [61]
[49, 52, 55, 58]
data in left of [55]
[49, 52]
data in left of [52]
[49]
not found
 
请输入猜测的数字：1
data in left of [49]
[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46]
data in left of [25]
[1, 4, 7, 10, 13, 16, 19, 22]
data in left of [13]
[1, 4, 7, 10]
data in left of [7]
[1, 4]
data in left of [4]
[1]
found 1

时间复杂度

• 时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n) 。
• 时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时， T(n)/f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ(f(n)) ,称 Ｏ(f(n))为算法的渐进时间复杂度，简称时间复杂度。

指数时间

• 指的是一个问题求解所需要的计算时间m(n)，依输入数据的大小而呈指数成长（即输入数据的数量依线性成长，所花的时间将会以指数成长

for (i=1; i<=n; i++)
       x++;
for (i=1; i<=n; i++)
    　for (j=1; j<=n; j++)
          x++;　

• 第一个for循环的时间复杂度为 Ο(n) ，第二个for循环的时间复杂度为Ο(\(n^2\))，则整个算法的时间复杂度为Ο(n+\(n^2\))=Ο(\(n^2\))

常数时间

• 若对于一个算法， T(n) 的上界与输入大小无关，则称其具有常数时间，记作 O(1) 时间。一个例子是访问数组中的单个元素，因为访问它只需要一条指令。但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作，或称 O(n) 时间。但如果预先知道元素的数量并假设数量保持不变，则该操作也可被称为具有常数时间。

对数时间

• 若算法的T(n) = O(\(log^n\))，则称其具有对数时间
• 常见的具有对数时间的算法有二叉树的相关操作和二分搜索。
• 对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小。
• 递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要 O(\(log^n\)) 的时间因为每次输出之前我们都将字符串砍半。 这意味着，如果我们想增加输出的次数，我们需要将字符串长度加倍。

线性时间

• 如果一个算法的时间复杂度为O(n)，则称这个算法具有线性时间，或O(n)时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。