/*     * 240.Search in a 2D Matrix II     * 2016-6-17by Mingyang     * From left-bottom to right-top     * 他这道题目虽说是用了BS，但是并不一定要有mid，这里就从最左下角到右上角     * 这个数大于同一列的，小于同一行的，只要跟target比较以后，就可以要么删除一列，要么删除一行--------找拐点     * 这个题目自己做的时候给出了一个nlog的方案，先是row从下往上走，在同一row里面再继续bs     * 但是这个题目的好方法就是从左下角出发，要么往右走，要么往上走     * 如果比目标大，表示我这一行都比目标大，那么我就往上走一个     * 如果比目标小，这一列都比目标小，那么往右走一个     */     public boolean searchMatrix2(int[][] matrix, int target) {            if (null == matrix || matrix.length == 0) {                return false;            }            int row = matrix.length - 1;            int col = 0;            while (row >= 0 && col < matrix[0].length) {                if (matrix[row][col] == target) {                    return true;                } else if (matrix[row][col] < target) {                    col++;                } else {                    row--;                }            }            return false;        }      /*      * 用了DC思想，就是根据与中间的大小，来舍弃一个部分的值      * Divide-Conquer，Based on the mid of the matrix, divide the whole matrix into four parts: left-top, left-bottom, right-top, right-bottom      * If the mid is smaller than target, abandon the left-top area, recursion from the other three areas.      * If the mid is larger than target, abandon the right-bottom area, recursion from the other three ares.      * Time Complexity formula：T(n) = 3T(n/2) + c      */     public boolean searchMatrixImprove(int[][] matrix, int target) {            if (null == matrix || matrix.length == 0) {                return false;            }            return helper(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);        }             private boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target) {            if (rowStart > rowEnd || colStart > colEnd) {                return false;            }            int rowMid = rowStart + (rowEnd - rowStart) / 2;            int colMid = colStart + (colEnd - colStart) / 2;            if (matrix[rowMid][colMid] == target) {                return true;            } else if (matrix[rowMid][colMid] > target) {                return helper(matrix, rowStart, rowMid - 1, colStart, colMid - 1, target) ||                        helper(matrix, rowMid, rowEnd, colStart, colMid - 1, target) ||                        helper(matrix, rowStart, rowMid - 1, colMid, colEnd, target);            } else {                return helper(matrix, rowMid + 1, rowEnd, colMid + 1, colEnd, target) ||                        helper(matrix, rowMid + 1, rowEnd, colStart, colMid, target) ||                        helper(matrix, rowStart, rowMid, colMid + 1, colEnd, target);            }        }