Description

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

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

target = 3
Output: true

target = 13
Output: false

矩阵中有序存地放着一些数字,查找是否存在某个数字。

Solution

下面代码使用两次二分查找,先找出在哪一行,再对该行进行二分查找。

亦有先计算元素个数:total = m x n,再对total进行二分查找的解法。 设二分时所以为index,对应元素坐标为(index/m, index%m)

 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
func searchMatrix(matrix [][]int, target int) bool {
    l, r := 0, len(matrix)-1

    // 先二分查找在哪一行
    for l < r {
        m := r - (r-l)/2

        if target >= matrix[m][0] {
            l = m
        } else {
            r = m - 1
        }
    }

    // conner case
    if l > len(matrix)-1 {
        return false
    }

    row := matrix[l]
    l, r = 0, len(row)-1

    // 再在对应行中进行二分查找
    for l <= r {
        m := l + (r-l)/2

        if target == row[m] {
            return true
        }

        if target > row[m] {
            l = m + 1
        } else {
            r = m - 1
        }
    }

    return false
}