一、导论
假设有一个有序数组array（注意：必须有序），我们要查找一个数在这个数组中的位置（index），如何查找？对于刚接触算法的大多数人，一般会采用直接遍历的方式查找数据。当人品爆发时，在该元素的数组中查找一个数只需找一次（遍历的第一个元素就是要找的）；但是呢，当我们查找的数据不幸是数组中的最后一个时，假若该数组有元素个数为n，那么我们要查找n次，如果n很大，那么查找该元素的时间会变得很长。其实，我们可以用分治策略来解决这样的一个问题，常见的就是“二分搜索法”。
二、简介
二分搜索也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
三、搜索过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
四、算法要求
1、必须采用顺序存储结构
2、必须按关键字大小有序排列
五、代码实现
C++实现二分搜索
六、时间复杂度分析
假设数据的规模为N，程序执行的比较次数表示为T(N)，假设程序查找的是一个不存在的数据，则此时执行的次数是最多的：
二分搜索的时间复杂度
当然也可以用小编上篇简书提及到的主定理法去求解时间复杂度，具体可看此链接算法之分治策略 - 简书
除此之外，还可以用小编之前有讲过的树的平均查找长度ASL来计算时间复杂度，这里就不分析了，有误请指正。
