JZ4 二维数组中的查找

题目： 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

本题不过是“JZ53 数字在升序数组中出现的次数”的翻版，只是从一维数组变成了二维数组

// 对于二维数组arr[3][4]，经常分不清行和列，行是3还是列是3?行列式，行在前，列在后，所以行是3，列是4。二维数组第一层遍历拿到的是每一行，然后对每一行进行遍历，拿到每一个元素。
int arr[][] = new int[][]{{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}};
System.out.println(arr.length); // 3
1
2
3

二维数组

解法一：暴力法

public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(array[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10

复杂度分析：
时间复杂度：O(NM)，遍历二维数组一次
空间复杂度：O(1)，不涉及额外内存空间

解法二：二分法

遍历二维数组拿到每一行，然后对每一行的一维数组进行二分查找

二分法的迭代写法和递归写法都写了。记得注意那两个边界问题。边界问题分析参见《JZ53 数字在升序数组中出现的次数》

public boolean Find(int target, int [][] array) {
        for(int[] arr:array){
            if(binarySearch(arr,target,0,arr.length)){
                return true;
            }
        }
        return false;
    }
     private boolean binarySearch(int[] arr,int k){
        int left=0;
        int right=arr.length;
        while(left<right){
            int mid =(left+right)/2;
            if(arr[mid]>k){
                right = mid;
            }else if(arr[mid]<k){
                left = mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
    private boolean binarySearch(int[] arr,int k,int left,int right){
        if(left>=right){
            return false;
        }
        int mid = (left+right)/2;
        if(arr[mid]>k){
            return binarySearch(arr,k,left,mid);
        }else if(arr[mid]<k){
            return binarySearch(arr,k,mid+1,right);
        }else{
            return true;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

复杂度分析：
时间复杂度：O(nlog2​m)，遍历二维数组拿到每一行，然后对每一行的一维数组进行二分查找
空间复杂度：O(1)，不涉及额外内存空间

解法三：线性查找

解法三属于是投机取巧。根据题目已知条件可得：从上到下递增，从左到右递增，可以把横向与纵向的交点看作是二分查找的中点。感觉是一种特殊的二分法。

比交点大，往右走一步，比交点小，往上走一步。

public boolean Find(int target, int [][] array) {
        int row = array.length;
        int col = array[0].length;
        for(int i=row-1,j=0;i>=0&&j<col;){
            if(array[i][j]>target){
                i--;
            }else if(array[i][j]<target){
                j++;
            }else{
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析：
时间复杂度：O(n+m)，遍历二维数组一次
空间复杂度：O(1)，不涉及额外内存空间

总结：
涉及数据结构：二维数组
涉及算法：二分法、迭代、递归