二分法体现了一种“分治”的思想。

二分查找

当需要在一个数组中查找某个元素的时候，我们自然而然地想到遍历整个数组，找到想要的元素就停止查找。这种方法的时间复杂度是O(n)，那么有没有一种更高效一点的方法呢？这时候就轮到二分查找登场了，二分查找的时间复杂度是O(logn)，显然是更高效的做法。不过使用二分查找需要有一个前提：数组必须是有序的。因为二分查找是通过比较来进行提速的，如果数组是乱序，或者元素无法进行比较，显然二分查找也就失效了。

int find(vector<int>& nums, int begin, int end, int target)
{
    if(begin > end) {
        return -1;
    }
    int mid = (end - begin) / 2 + begin;
    if(target == nums[mid]) {
        return mid;
    }
    return target < nums[mid] ? find(nums, begin, mid - 1, target) :
        find(nums, mid + 1, end, target);
}

上面代码是一种二分查找的递归实现，begin表示要查找的开始位置，end表示要查找的最后位置，如果begin大于end，显然整个元素就不在数组中，返回-1表示没有找到。
计算中间位置，如果中间位置的元素正好等于要查找的元素，就返回这个位置，否则的话，比较一下目标元素是比中间位置的元素大了还是小了，小了的话，说明在前半段中，否则相反。

总结：对于有序数组来说，二分查找是一种比较好的算法。

二分插入

leetcode上有一道简单难度的题，找到目标值，返回索引，如果不存在，则返回插入位置，要求时间复杂度在O(logn)。很明显是让使用二分法来做。

int insert(vector<int>& nums, int begin, int end, int target)
{
    if(begin == end) {
        return begin;
    }
    int mid = (end - begin) / 2 + begin;
    if(target == nums[mid]) {
        return mid;
    }
    return target < nums[mid] ? insert(nums, begin, mid, target) :
        insert(nums, mid + 1, end, target);
}