image.png

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

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

示例 1：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：


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

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

image.png

Swift

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if matrix.isEmpty || matrix.first!.isEmpty {
            return false
        }

        for row in matrix {
            if let fisrt = row.first, fisrt <= target,
               let right = row.last, right >= target
            {
                if fisrt == target || right == target {
                    return true
                }

                var left = 0, right = row.count - 1

                while left <= right {
                    let mid = left + (right - left) / 2

                    if row[mid] > target {
                        right = mid - 1

                    } else if row[mid] < target {
                        left = mid + 1
                    } else {
                        return true
                    }
                }
            }
        }

        return false
    }
}

print(Solution().searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3))

print(Solution().searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]], 5))

Dart

class Solution {
  bool searchMatrix(List<List<int>> matrix, int target) {
    if (matrix.isEmpty || matrix.first.isEmpty) {
      return false;
    }

    for (var row in matrix) {
      int fisrt = row.first;
      int right = row.last;

      if (fisrt == target || right == target) {
        return true;
      }

      if (fisrt < target && right > target) {
        var left = 0, right = row.length - 1;

        while (left <= right) {
          int mid = (left + (right - left) / 2).toInt();

          if (row[mid] > target) {
            right = mid - 1;
          } else if (row[mid] < target) {
            left = mid + 1;
          } else {
            return true;
          }
        }
      }
    }

    return false;
  }
}

main() {
  print(Solution().searchMatrix([
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
  ], 3));

  print(Solution().searchMatrix([
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
  ], 5));
}