面试题4：二位数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
1，使用二分查找，第一个for循环用于控制行，在每一行作二分查找，循环指针满足大小关系，如果目标值大于当前值，到中间值后面去查找，如果目标值小于当前值就去前面查找，否则就找到跳出去。一直没有跳出去就返回false
2，首选选取二位数组右上角的数，如果当前位置的数恰好等于要找的数，则退出，如果当前元素大于要找的数则去掉第一行，也就是行数+1，如果小于要找的数，则去掉当前列，即列数减一。

/**
     * 从右上角元素开始比较，相等则是
     * 大于该元素就可以去掉上面一行
     * 小于该元素则可以去掉右边一列
     * 下标作为变量进行移动
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int [][] array) {
        boolean flag = false;
        int row = 0;
        int column = array[0].length-1;
        /***
         * 注意元素列元素下标包括0
         */
        while (row < array.length && column >= 0) {
            if (target == array[row][column]) {
                flag = true;
                return flag;
            } else if (target < array[row][column]) {
                --column;
            }else {
                ++row;
            }
        }
        return flag;
    }

    /**
     * 二分法查找
     * @param target
     * @param array
     * @return
     */
    public boolean Find2(int target, int[][] array) {
        if (array != null && array.length > 0) {
            // 注意high在循环外，一旦值更新下次循环不会再被初始化，可减少比较次数
            int high = array[0].length - 1;
            for (int i = 0; i < array.length; i++) {
                int low = 0;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (target > array[i][mid]) {
                        low = mid + 1;
                    } else if (target < array[i][mid]) {
                        high = mid - 1;
                    } else {
                        return true;
                    }
                }
            }
            return false;
        }
        return false;
    }