算法：二分查找

前言：最近小编在看《算法图解》，将会总结一系列算法相关的文章。
关于算法的系列文章，小编将准备分“三步”来编写：

• 第一步：描述算法，并提供“图解”及示例Demo。
• 第二步：用大O表示法讨论运行时间。
• 第三步：分析该算法能解决的实际问题。
  （PS：示例代码将基于Python编写）

---

本篇将介绍二分查找与大O表示法，并为后续的算法文章打下算法基础。

一、算法简介

算法，简单来说，就是一组完成任务的指令。任何代码片段都可视为算法。

算法的用途主要有两个方面：

• 一：提高代码的运行速度，优化业务逻辑。 => 已达到提高代码质量的目的。
• 二：解决实际应用问题。 => 已达到完成业务需求的目的。

算法的用途	目的
提高代码运行速度，优化业务逻辑	提高代码质量
解决实际应用问题	完成业务需求

二、二分查找

问题：假设有一个有序数组（前提：有序数组），我们要查询一个数在这个数组中的位置（index），我们应该如何查找？

先介绍一个简单而暴力的查找方式：直接遍历一遍这个数组，找到对应的数后再返回index。这个方法我们称之为——简单查找。

2.1 简单查找：

直接遍历数组查找元素。很简单很暴力。

基于Python的算法：

def easy_search(list, item):
    for index in range(len(list)):
        if list[index] == item:
            return index
    return None

测评：
简单查找在运气好时（即遍历的第一个元素即为该数），只需要查找一次。
但是当如果所找元素在数组末尾时，就要一直遍历到最后一个元素才能找到那个数。n个元素的数组要找n次。

这显然效率会不高，这时候我们可以使用：二分查找法。

2.2 二分查找：

二分查找，顾名思义，每次查找将数组分成两部分，从中间开始找。

• 如果发现数比中间数大，即数在中间数与最大数之间，就修改low的值。再对比中间值。
• 如果发现数比中间数小，即数在最小数与中间数之间，就修改high的值。再对比中间值。

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

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

这样，每次循环就能舍去一半的元素，大大提高了查找的效率。这就是二分查找法。

三、大O表示法

时间复杂度由大O表示法描述。

• 时间复杂度描述的是算法的运行效率；
• 时间复杂度指的并非具体时间，而是操作数的增速。

运用简单查找算法，在n个元素的数组中查找一个数，情况最遭时，需要n步，所以简单查找的时间复杂度是O(n)；

运用二分查找算法，在n个元素的数组中查找一个数，情况最遭时，需要(log n)步，所以二分查找的时间复杂度是O(log n)。

工程源码：QiAlgorithms