【基础篇 - Day 26】 2020-11-26 - 74. 搜索二维矩阵

题目描述

入选理由

1. 熟悉二分

题目描述

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

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

示例 1：


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


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

输入：matrix = [], target = 0
输出：false


提示：

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

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

我的回答

解法一

时空复杂度

时间复杂度：O(logn)

空间复杂度: O(1)

var searchMatrix = function (matrix, target) {
    if (!matrix.length) return false
    let lo = 0
    let m = matrix.length
    let n = matrix[m - 1].length
    let hi = m * n - 1
    while (lo <= hi) {
        const mid = Math.floor(lo + (hi - lo) / 2)
        let x = mid % n
        let y = Math.floor(mid / n)
        if (matrix[y][x] === target) return true
        if (matrix[y][x] < target) {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return false
};

参考回答

• 官方题解 (opens new window)