简介：二分查找法，也叫折半查找法。是计算机中最基本、最有用的基础算法之一。它讲述的是在有序的集合中搜索特定目标的过程。
实现方法：首先将序列进行排序，将中间位置的值与目标值进行比较，如果相等，则查找成功；如果不等，则根据记录到的中间位置将序列分成前后两个子序列，比较目标值与中间位置值的大小，判断目标值所在的子序列，继续查找该序列，舍弃另外一个子序列。重复以上过程，直到查找成功，或者子序列不存在的时则表示目标值查找不成功。
二分查找法一般分成三个步骤：
1、预处理阶段：主要是对原集合进行预处理。例如数列是无序的，需要先进行排序。
2、查找阶段：使用递归或者循环的方式，把查找的空间划分成两半。
3、后处理阶段：清除掉不符合需求的一半，在剩余的一半空间中确定可行的候选者。
二分法模板：基于对左、中、右索引的分配，以及终止条件和后处理的不同，可以总结出以下三个简易模板。
基础模板一：
初始条件：left=0, right=length-1
终止条件：left>right
向左查找：right=mid-1
向右查找：left=mid+1
说明：基础模板，不需要与查找元素两侧进行比较来确定查找条件，也不需要后处理操作。到达末尾没找到，则说明数列中没有目标值。
基础模板二：
初始条件：left=0, right=length-1
终止条件：left+1==right
向左查找：right=mid
向右查找：left=mid
说明：需要使用搜索元素的左右邻居来确定查找方向是向左还是向右，因此它需要保证空间的每个步骤内至少有3个元素。当剩余2个元素的时候结束循环或者递归，而且还需要判断这2个元素是否符合条件。
基础模板三：
初始条件：left=0, right=length
终止条件：left==right
向左查找：right=mid
向右查找：left=mid+1
说明：需要使用搜索元素的右邻居来确定查找方向是向左还是向右，因此它需要保证空间的每个步骤内至少有2个元素。当剩余1个元素的时候结束循环或者递归，而且还需要判断这个元素是否符合条件。
时间复杂度：O（logn）
空间复杂度：O（1）
