【剑指offer-Java版】03二维数组中的查找

╰半橙微兮° 2022-08-21 08:52 46阅读 0赞

给定二维数组，和一个整数，二维数组的行从左到右递增，列从上到下递增。  
查找该二维数组，看是否有和给定整数相等的值

技巧就是找到一个位于\[i\]\[j\]的值，通过该值判断给定值可能存在于数组的哪一独立部分  
满足这个条件的\[i\]\[j\]有两对，一个是左下角一个是有上角

假设以右上角为例，那么可以把\[i\]\[j\]所在的行\[0 .. i-1\]看做是一棵树的左子树，所在列\[j+1 … n\]看做是右子树，数组的其他部分忽略掉  
那么位于\[i\]\[j\]的元素可以看做是二叉排序树的树根：因为左子树都小于根节点，右子树都大于根节点  
查找过程就相当于决定目标结点是在左子树还是在右子树中  
但是和一般的二叉查找不同的是，此处的左右子树都是需要根据\[i\]\[j\]的位置不断变化的，每换一个位置就对应一棵新的二叉树

public class _Q03 {
        public static void main(String[] args) {
    
            int matrix[][] = { 
                    {
       1, 2, 8, 9},
                    {
       2, 4, 9, 12},
                    {
       4, 7, 10, 13},
                    {
       6, 8, 11, 15}
            };
    
            int target = 5;
    
            System.out.println(find(matrix, 4, 4, target));
    
        }
    
        static boolean find(int matrix[][], int row, int col, int target){
            boolean isFound = false;
    
            if((matrix == null) || (row <= 0 ) || (col <= 0)) { return isFound;}
    
            int xIndex = 0;
            int yIndex = col-1;
    
            while((xIndex<row) && (yIndex>=0)){
                if(matrix[xIndex][yIndex] == target){
                    isFound = true;
                    break;
                }else if(matrix[xIndex][yIndex] > target){
                    yIndex--;
                }else if(matrix[xIndex][yIndex] < target){
                    xIndex++;
                }
            }
    
            return isFound;
        }
        }