/*

     * 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);

            }

        }