python 二分法查找实例（递归、循环）

二分法，主要应用于有序序列中，原理是每次查找都将原序列折半，逐渐缩小查找范围的一种算法。

需求

要求在一个有序序列中，例如[0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99]，查找一个数字，如果找到则打印该数字，如果找不到，则输出“not found！”

递归方式

递归，是在函数中自身调用自身的一种情况，直到有一个明确的退出条件成立后结束相互调用。递归是一种很容易理解某类问题的方式，但是不是特别高效，因为每次调用自身时，都会在内存中创建一个新的内存空间，当不断循环调用非常多次时，是非常耗内存的。

#!/usr/bin/env python # -*- coding: utf-8 -*- def recursion_search(data_source, find_n): mid = len(data_source) / 2 if len(data_source) >= 1: if find_n > data_source[mid]: recursion_search(data_source[mid + 1:], find_n) elif find_n < data_source[mid]: recursion_search(data_source[:mid], find_n) else: print data_source[mid] else: print "not found !" if __name__ == '__main__': test_array = range(0, 100, 3) recursion_search(test_array, 99)

循环方式

#!/usr/bin/env python # -*- coding: utf-8 -*- def loop_search(data_source, find_n): while len(data_source): mid = len(data_source) / 2 if find_n < data_source[mid]: data_source = data_source[:mid] elif find_n > data_source[mid]: data_source = data_source[mid + 1:] else: print data_source[mid] break else: print "not found !" if __name__ == '__main__': test_array = range(0, 100, 3) loop_search(test_array, 99)

 

---

***微信扫一扫，关注“python测试开发圈”，了解更多测试教程！***

转载于:https://www.cnblogs.com/guanfuchang/p/5895422.html