240. 搜索二维矩阵 II(二分查找)

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[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

示例 2：

输入：matrix = [[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 = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

方法一：(二分查找)

 1 1 class Solution {
 2  2 public:
 3  3     bool binarySearch(const vector<int> &vec, int target) {
 4  4         int left = 0;
 5  5         int right = vec.size() - 1;
 6  6         while (left <= right) {
 7  7             int mid = left + (right - left) / 2;
 8  8             if (vec[mid] == target) {
 9  9                 return true;
10 10             }
11 11             if (vec[mid] < target) { // 目标值在区间[mid + 1, right]
12 12                 left = mid + 1;
13 13             } else { // 目标值在区间[left, mid - 1]
14 14                 right = mid - 1;
15 15             }
16 16         }
17 17         return false;
18 18     }
19 19     bool searchMatrix(vectorint>>& matrix, int target) {
20 20         if (matrix.size() == 0 || matrix[0].size() == 0) {
21 21             return false;
22 22         }
23 23         int n = matrix.size();
24 24         int m = matrix[0].size();
25 25         // 遍历每一行查找目标值是否存在
26 26         for (int i = 0; i < n; i++) {
27 27             // 如果只存在一列,查找每一行元素是否目标值一样
28 28             if (m == 1) {
29 29                 if (matrix[i][0] == target) {
30 30                     return true;
31 31                 }
32 32             } else { // 二维数组多于1列,查找每一行是否存在目标值
33 33                 if (binarySearch(matrix[i], target)) {
34 34                     return true;
35 35                 }
36 36             }
37 37         }
38 38         return false;
39 39     }
40 40 };

方法二：(Z行查找)

 1 class Solution {
 2 public:
 3     bool searchMatrix(vectorint>>& matrix, int target) {
 4         if (matrix.size() == 0 || matrix[0].size() == 0) {
 5             return false;
 6         }
 7         // 初始位置左下角
 8         int x = matrix.size() - 1;
 9         int y = 0;
10         // 只要不超过右上角
11         while (x >= 0 && y <= matrix[0].size() - 1) {
12             // 如果当前位置元素比目标值大,则目标在上一行
13             if (matrix[x][y] > target) {
14                 x--;
15             } else if (matrix[x][y] < target) { // 当前位置元素比目标值小,则目标值在下一列
16                 y++;
17             } else {
18                 return true;
19             }
20         }
21         return false;
22     }
23 };