LeetCode 第 240 题：搜索二维矩阵 II

题目描述
给定一个 m x n 的矩阵 matrix，该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。
  要求编写一个高效的算法来搜索矩阵中是否存在目标值 target。如果存在返回 true，否则返回 false。

解题思路
由于矩阵的行和列都是有序的，我们可以利用这种特性从矩阵的右上角（或左下角）开始搜索。以右上角为例：

• 如果当前元素等于 target，直接返回 true。
• 如果当前元素大于 target，说明目标值不可能在当前元素的同一列（因为列向下递增），因此向左移动一列。
• 如果当前元素小于 target，说明目标值不可能在当前元素的同一行（因为行向左递减），因此向下移动一行。
  这样每一步都能排除一行或一列，时间复杂度为 O(m + n)。

详细步骤

1. 初始化指针：从矩阵的右上角开始，即行索引 row = 0，列索引 col = n - 1。
2. 循环搜索：当指针在矩阵范围内时（row < m 且 col >= 0）：
   • 如果 matrix[row][col] == target，返回 true。
   • 如果 matrix[row][col] > target，说明目标值可能在当前元素的左侧，列索引 col 减 1。
   • 如果 matrix[row][col] < target，说明目标值可能在当前元素的下方，行索引 row 加 1。
3. 终止条件：如果指针越界仍未找到目标值，返回 false。

示例演示
以矩阵为例：

matrix = [
  [1,  4,  7,  11],
  [2,  5,  8,  12],
  [3,  6,  9,  16],
  [10,13,14,17]
]

搜索 target = 5：

1. 从右上角 11 开始，11 > 5，向左移动到 7。
2. 7 > 5，向左移动到 4。
3. 4 < 5，向下移动到 5。
4. 5 == 5，返回 true。

关键点

• 选择右上角或左下角作为起点，可以保证每次移动能排除一行或一列。
• 避免暴力搜索（O(mn)）或二分查找的复杂实现，该方法简洁且高效。