算法篇-python查找算法

上一篇的递归算法中，了解到算法的复杂度。递归就是在函数中调用本身。

在汉诺塔游戏例子中，如果你需要移动的盘子很多时，程序运行就会消耗很长时间来计算结果。可以回顾下 —>算法篇-python递归算法

用递归打印斐波那契数列，你会发现，即使n只有几十的时候，你的计算机内存使用量已经飙升了。

可以结合 生成器 优化下程序，不管n有多大，都不会出现卡顿。

有一点，关于递归次数，python中有个限制，可以通过sys模块来解决。

python 查找算法

查找就是根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。

知道了查找的定义，试着用一个简单的例子，能想到 for 循环么？

有没有发现，是不是两两比较就能找到啦。假设列表中有很多元素，再用 for 循环来查找，得到结果的时间会不会更长。

算法的复杂度是渐进的，即对于一个大小为n的输入，如果它的运算时间为n3+5n+9，那么它的渐进时间复杂度是n3

刚刚用的 for 循环 来查找，它的时间复杂度O(n)

有没有继续优化的查找算法呢？

可以设想下，在列表中元素能一半一半的查找，再来查找目标值，是不是就会快一些。

接着就是~

二分查找

上面说到，一半一半的查找，看目标值在左边一半还是右边一半，然后替换左端点或者右端点，继续判断。

直接上例子啦