算法分享之二分查找

在有序序列之中要找到某一个数，一般暴力的方法就是遍历这个序列，查找是否符合，当然这对于常规数组而言就是一个而已，不算大，但是如果每次检查都要花费很多时间而非，那么从优化到就显得很重要了。

二分查找的常规思路是，对将序列从中间分成大小两份，然后判断中点，根据中点与所求值的大小判断所有应该在左边的小区间还是右边的大区间，并重复如此的操作。因此区间不断连除2，而区间大小为，则相当于最坏情况下复杂度就是对连除2到最小，即.

牛客网应用二分法的题目很多，比如求解立方根 、牛牛晾衣服 、Redraiment的走法 、二维数组中的查找 。

当然二分的思想不仅可以应用于一维序列，也可以应用于二维数组，我们看下面这道题：（完整的题解可以参考这篇题解 。

既然矩阵里面的元素是有序且无重复的，我们可以好好利用一下。

首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：
左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。
我们可以在查找时使用二分法：
首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  //优先判断特殊
            return false;
        int n = array.size();
        if(array[0].size() == 0)  
            return false;
        int m = array[0].size();
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //从最左下角的元素开始往左或往上
            if(array[i][j] > target)   //元素较大，往上走
                i--;
            else if(array[i][j] < target) //元素较小，往右走
                j++;
            else
                return true;
        }
        return false;
    }
};