剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [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]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

1
2
0 <= n <= 1000
0 <= m <= 1000

解法1：暴力双循环

略

解法2：按行二分查找

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
public boolean findNumberIn2DArray(int[][] matrix, int target) {
    boolean flag = false;
    //对每一行进行二分查找
    for(int[] nums : matrix){
        flag = binarySearch(nums,target);
        if(flag){
            flag = true;
            break;
        }
    } 
    return flag;
}
//二分查找
boolean binarySearch(int[] nums,int target){
    int left = 0;
    int right = nums.length - 1;
    
    while(left <= right){
        int mid = left + (right - left) /2;
        if(nums[mid] < target){
            left = mid + 1;
        }else if (nums[mid] > target){
            right = mid - 1;
        }else{
            return true;
        }
    }
    return false;
}

解法3：线性搜索

由于二维数组按行按列递增，所以对于在二维数组中的每个元素都有如下性质

  • 该元素上边的元素都比他小
  • 该元素右边的元素都比他大

所以可以从数组左下角开始搜索

  • 如果当前数字大于target则向上搜索
  • 如果当前数字小于target则向右搜索
  • 如果查找到该元素则返回
  • 如果数组越界，则返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean Find(int target, int [][] array) {
    int rowBound = array.length;
    int colBound = array[0].length;
    
    //定位元素在左下角
    int row = rowBound - 1;
    int col = 0;
    
    while(row >= 0 && col < colBound){
        int temp = array[row][col];
        if(temp == target){
            return true;
            //当前值小于目标值，向右移动
        }else if(temp < target){
            col++;
            //当前值大于目标值，向上移动
        }else{
            row--;
        }
    }
    return false;
         
}