搜索二维矩阵②

package com.memorys.algorithm.year2021.month08;

/** * * @Description: * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： * * 每行的元素从左到右升序排列。 * 每列的元素从上到下升序排列。 * * 作者：力扣 (LeetCode) * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmlwi1/ * * * @Date 2021-08-07 23:09 * @Description */public class SearchMatrix {
    public static void main(String[] args) {
        int [][] matrix = {                    {1,4,7,11,15},                    {2,5,8,12,19},                    {3,6,9,16,22},                    {10,13,14,17,24},                    {18,21,23,26,30}                };        int target = 31;        boolean result1 = SearchMatrix1(matrix, target);        System.out.println(result1);
        boolean result2 = SearchMatrix2(matrix, target);        System.out.println(result2);
    }

    /**     * @CreateDate 2021-08-07 23:19     * @param matrix     * @param target     * @Description     * 找到目标数，常用的算法就是2分法，     * 因此，对每一行进行二分查找，一直到找出结果位置     *     * 时间复杂度为O(m㏒n)     *     * @Return boolean     */    public static boolean SearchMatrix1(int[][] matrix, int target){

        for (int i = 0 ;i < matrix.length; i++) {           int arr[] = matrix[i];           boolean result = binarySearch2(arr, target,0,arr.length - 1);           if (result){               return result;           }        }        return false;    }
    private static boolean binarySearch2(int[] arr, int target, int from, int to){        if (to < from){            return false;        }        if (to == from){            if (arr[to] == target){                return true;            }else {                return false;            }        }        if (to - from == 1){            if(arr[to] == target ||  arr[from] == target){                return true;            }else {                return false;            }        }
        int middle = from + (to - from)/2;        if (arr[middle] == target){            return true;        }        if (arr[middle] > target){            return binarySearch2(arr,target,from,middle);        }        if (arr[middle] < target){            return binarySearch2(arr,target,middle,to);        }        return false;    }


    /**     * @CreateDate 2021-08-08 10:02     * @param matrix     * @param target     * @Description :     * 通过题目的描述可以看出，对于矩阵的某一个节点来说，、     * 左上角的肯定比它小，右下角的肯定比它大，     * 但是左下角和右上角和它的大小关系是不确定的。     *     * 因此不能用从中间查找的方法来查找，只能尽可能的缩小不确定的范围的个数。     * 不确定的在左下角以及右上角。     * 同时因为要判断大小，因此需要，比自己大的都在同一个方向，比自己小的在另外一部分方向。     * 因此坐上，右下不符合要求。     * 因此我们从最左下角或者最右上角开始找。     * 这里拿最左下角当做例子。     * 上边的都比自己小，右边的都比自己大。     * 因此目标值比自己大，那就往右找，目标值比自己小就往上找即可。     *     * 时间复杂度为：O(m+n)     *     * @Return boolean     */    public static boolean SearchMatrix2(int[][] matrix, int target){        int width = 0;        int length = matrix.length - 1;        while (matrix[length][width] != target){            int num = matrix[length][width];            if (matrix[length][width] == target){                return true;            }
            if (matrix[length][width] > target){                length = length - 1;                if (length == -1){                    return false;                }            }else if (matrix[length][width] < target){                width = width + 1;                if (width == matrix[0].length){                    return false;                }            }        }
        return true;    }

}