《算法图解》读书笔记1-二分和大O

算法是一组完成任务的指令

为什么要学习算法

这次是我第二次读《算法图解》，当我第一次看这本书的时候，我更兴奋于书中有什么内容，迫不及待的去过内容，学习那些算法概念。但当我第二次准备开始读这本书的时候，我脑海中出现的了一个问题：“为什么要学习算法？”，这个问题也许会有人和我一样，之前根本没有好好的去思考，只是知道，作为一个程序员我应该学习算法。当然，能够有这个觉悟，说明我们还算是个合格的程序员。

但是，不妨认真思考一下，为什么要学习算法？算法应该怎么学？

首先，我觉得算法是一种思想，并不只是一段代码。它不拘泥于形式，而在于我们去如何运用这种思想。我们目前接触到的算法，都可以算作是前辈们通过不断的实践经验而得出的一种总结。算法可以帮助我们写出性价比更高的程序，来应对实际生产中的种种挑战。既然算法是一种思想，那么他就不会是一陈不变的，在学习的过程中，要保持一颗怀疑的态度，不断的试图对已有算法举反例验证。若能针对已有的算法提出自己的改进，那真是一件有意义的事情。

再者，算法好比我们学语言的时候，需要先学习语法，才能够将学到的词汇灵活的整理成话语。说话的方式千奇百怪，不同的场合下，我们会选择说合适的话。算法也一样，不能单纯的从运行时间上对比两个算法的优劣，有的场合内存要求高，时间要求不高，这时候可以能就需要牺牲时间来满足内存要求。将不同的算法，放置到不同的生产要求环境中，再选择适宜的算法，这是我接下来学习每个算法应该思考的出发点。

最后，学好算法，有助于提升我们的技术水平，找到更好的工作机会，赚更多的钱。最后走上人生巅峰，迎娶白富美。[自行脑补……]

二分查找

二分查找算法（binary search），也称为折半搜索（英语：half-interval search），对数搜索（英语：logarithmic search）。是一种在有序数组中查找某一特定元素的搜索算法。

算法前提：

• 有序数组

算法步骤图示：

算法 python3 代码实现：(针对元素互不相同的情况，若有连续相同的，见讨论区补充)

• 递归实现

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    mid = (low + high)//2
    if list[mid] > item:
        return binary_search(list[:mid], item)
    if list[mid] < item:
        return binary_search(list[mid:], item)
    return mid

• 循环实现

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high)//2
        if list[mid] < item:
            low = mid + 1
        elif list[mid] > item:
            high = mid - 1
        else:
            return mid

算法复杂度：

• 最优时间复杂度：O(1)
• 最坏时间复杂度：O(logn)
• 平均时间复杂度：O(logn)
• 空间复杂度：迭代实现：O(1)；循环实现：O(logn)

大 O 表示法

大 O 表示法指出了算法的效率。

Wikipedia：大 O 符号（英语：Big O notation），又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。

每个算法都可以通过一个数学公式表达，大 O 表示法，标记的是一个函数中起主导作用的一项，而其他项可以被忽略。举个例子，解决一个规模为 n 的问题所需步骤的数目可以表示为：

当 n 增大时，n 平方项将主导整个算式结果的走向，其他项的影响将越来越小，甚至忽略不计。用大 O 表示法就是：

我们就说该算法具有平方阶的时间复杂度。

常用函数阶