LeetCode

Leetcode 74-搜索二维数组

两次二分查找 VS 一次二分查找

Posted by 刘知安 on 2019-11-09
文章目录
  1. Leetcode 74-搜索二维数组
    1. 1. 题目描述
    2. 2. 思路
    3. 3. 代码

Leetcode 74-搜索二维数组

1. 题目描述

编写一个高效的算法来判断?m x n?矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
示例?1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

2. 思路

这个题目思路也很清晰，肯定是采用两次二分查找，先二分查找到所在的行，再在这行里二分查找。

我觉得这个题目的亮点就在于在查找所在的行时略微有点不一样，例如：

1
2
3
4
5
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

假如target=13，如果在行的那轮二分查找时，我们真的只naive地二分查找，此时中值为20，哦，我要找的值比中值小，右指针指向mid的前一位。
这样就错了！！！我们的target反而是落在了mid所在的那行，所以这里不仅要和行的尾部元素进行对比，也不能忘了行的头元素。

在第一次提交代码的时候，我的确考虑了这一点，不过当时用的是mid那一行的上一行的尾元素。代码大概长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 while (row_b < row_e) {
	if (target == matrix[row_m][cols - 1])
		return true;
	else if (target > matrix[row_m][cols - 1])
		row_b = row_m + 1;
	else if (target < matrix[row_m][cols - 1]) {
		// 如果比上一列的最后一个大
		if (target > matrix[row_m - 1][cols - 1])  // Notice: 数组越界异常
			row_e = row_m;
		else
			row_e = row_m - 1;
	}
	row_m = (row_b + row_e) / 2;
}

这里有个严重的错误，当target是第一行的元素时，必然会存在数组越界，所以要略微改一下。
改成不去比较mid行的上一行的尾元素，而比较mid所在行的头元素。

3. 代码

两次二分查找AC代码，执行用时超过100%，内存消耗超过37%，这里的时间复杂度为O(log(M*N)),空间复杂度O(1)。
这里用的是两次二分查找，所以虽然是常数级别的内存开销，还是偏大！因为，可以完全看作是一次二分查找啊！！！

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * @ClassName Search2DMatrix
 * @Deacription // TODO
 * @Author LiuZhian
 * @Date 2019-11-09 11:23
 * @Version 1.0
 **/

public class Search2DMatrix74 {
    private int rows, cols;
    private int[][] m;

    public boolean searchMatrix(int[][] matrix, int target) {
        // 特殊情况
        if (matrix.length == 0) // 空数组
            return false;
        rows = matrix.length;
        cols = matrix[0].length;
        m = matrix;


        int row_b = 0, row_e = rows - 1, row_m = (row_b + row_e) / 2;

        while (row_b < row_e) {
            if (target == matrix[row_m][cols - 1])
                return true;
            else if (target > matrix[row_m][cols - 1])
                row_b = row_m + 1;
            else if (target < matrix[row_m][cols - 1]) {
                // 如果比row_m行的的第一个还要小
                if (target < matrix[row_m][0])
                    row_e = row_m-1;
                else
                    row_e = row_m;
            }
            row_m = (row_b + row_e) / 2;
        }
        // 最后在row_m行找target即可
        return findInRow(row_m, target);
    }

    // 在第i行中找target
    private boolean findInRow(int row, int target) {
        int col_b = 0, col_e = cols - 1, col_m;
        while (col_b <= col_e) {
            col_m = (col_b + col_e) / 2;
            if (m[row][col_m] == target)
                return true;
            else if (target < m[row][col_m])
                col_e = col_m - 1;
            else
                col_b = col_m + 1;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {8, 9, 9, 9}, {10, 11, 16, 20}, {23, 30, 34, 50}, {23, 30, 34, 50}};
        Search2DMatrix74 s = new Search2DMatrix74();
        System.out.println(s.searchMatrix(matrix, 1));
        
    }
}

下面是官方提供的一次二分查找代码：

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
class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    if (m == 0) return false;
    int n = matrix[0].length;

    // 二分查找
    int left = 0, right = m * n - 1;
    int pivotIdx, pivotElement;
    while (left <= right) {
      pivotIdx = (left + right) / 2;
      pivotElement = matrix[pivotIdx / n][pivotIdx % n];
      if (target == pivotElement) return true;
      else {
        if (target < pivotElement) right = pivotIdx - 1;
        else left = pivotIdx + 1;
      }
    }
    return false;
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/
来源：力扣（LeetCode）

666.

FEATURED TAGS
LeetCode
FRIENDS