74. Search a 2D Matrix 在二维矩阵中搜索

题目

编写一个高效的算法，在 m*n 矩阵中搜索目标值 target。这个矩阵有以下特性。

• 每行数字从左到右升序排列
• 每行第一个整数大于前一行的最后一个。

解析

根据这个矩阵的性质，我们可以根据行首元素，先确定数据在哪一行，然后在当前行中继续搜索。
两次搜索都以二分法的方式进行。

伪代码

// 搜索可能在哪一行
if target < m[0][0] || target > m[m][n]
   return false
// 判断是否在最后一行
if target > m[row][0]
  hangsousuo
// 二分搜索
for i<j
  mid := i+j/2
  if m[mid][0] >= target && m[mid+1][0] < target
    hangsousuo
  if m[mid][0] < target
    i = mid + 1
  if m[mid][0] > target
    j = mid - 1

代码

func searchMatrix(matrix [][]int, target int) bool {
    m := len(matrix)
    n :=len(matrix[0])
    if target < matrix[0][0] || target > matrix[m-1][n-1] {
        return false
    }
    i:=0
    j:=m-1
    for i<j {
        mid := (i+j) / 2
        if target >= matrix[mid][0] && target < matrix[mid+1][0] {
            return searchRow(matrix, target, mid)
        }
        if target < matrix[mid][0] {
            j=mid-1
        }
        if target > matrix[mid][0] {
            i=mid+1
        }
    }
    return searchRow(matrix, target, i)
}

func searchRow(matrix [][]int, target int, row int) bool {
    n := len(matrix[0])
    n--
    if target < matrix[row][0] || target > matrix[row][n] {
        return false
    }
    i:=0
    j:=n
    for i<j {
        mid := (i+j)/2
        if target == matrix[row][mid] {
            return true
        }
        if target < matrix[row][mid] {
            j = mid-1
        }
        if target > matrix[row][mid] {
            i=mid+1
        }
    }
    return matrix[row][i] == target
}

后记

1. 我们敢直接使用 m[mid+1]，而不担心越界，因为有 i<j 的限制。在 i<j 的情况下，mid+1 始终有值。
2. 二分法，在 i< j 的条件下，指针悬停的位置很有意义，代表最后一个未进行判断的数据。