//二分法查找,从中间查起,然后向两边扩散
//时间复杂度图片说明

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null || array.length == 0||array[0] == null || array[0].length == 0){
            return false;
        }
        return find2(array,0,array[0].length-1,0,array.length-1,target);
    }
    public boolean find2(int[][] arr, int left, int right, int top, int low, int n) {
        boolean result = false;
        int midL = (left + right) / 2;
        int midW = (top + low) / 2;
        if (n == arr[midW][midL]) {
            result = true;
//            System.out.printf("第%d行:\t,第%d列\n", midL+1, midW+1);
        }
        if (n > arr[midW][midL]) {
            if (right - midL > 0) {
                //往右找
                result = result || find2(arr, midL + 1, right, top, low, n);
            }
            if ((low - midW) > 0) {
                //往下找
                result = result || find2(arr, left, right, midW + 1, low, n);
            }

        }
        if (n < arr[midW][midL]) {
            if ((midL - left) > 0) {
                //往左找
                result = result || find2(arr, left, midL - 1, top, low, n);
            }
            if ((midW - top) > 0) {
                //往上找
                result = result || find2(arr, left, right, top, midW - 1, n);
            }
        }
        return result;
    }
}