算法题-12

给你一个满足下述两条属性的m x n整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。

• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数target，如果target在矩阵中，返回true；否则，返回false。

关键条件我们可以看到，每行递增，每行第一个数>上一行的最后一个数，这意味着整体矩阵有序，那我们应该想如何映射回一维矩阵。

我们先确定了左右边界，let left = 0，let right = m * n - 1，然后发现，行列正好与中值存在关系，

row = Math.floor(mid / n)
col = mid % n

示例1：left = 0，right = 11 row = 3 col = 4,整体代码与搜索插入类似

var searchMatrix = function(matrix, target) { const m = matrix.length const n = matrix[0].length let left = 0 let right = m * n - 1 while(left <= right) { const mid = Math.floor((left + right) / 2) const row = Math.floor(mid / n) const col = mid % n const value = matrix[row][col] if(value === target) { return true } else if(value < target) { left = mid + 1 } else { right = mid - 1 } } return false }