原题链接：
https://leetcode.cn/problems/search-a-2d-matrix-ii/
解题思路：
- 每一行都是递增的，那就意味着可以对每一行做二分查找
- 如果找到了
target就返回true，如果查找完所有行都没有找到target，返回false - 如何二分查找：
- 首先声明左边界
let left = 1，右边界let right = 1000 - 计算它们的中间值，
const middle = (left + right) >> 1，或者可以用const middle = Math.floor((left + right) / 2) - 如果中间值等于
target，说明找到了target - 如果中间值大于
target，说明target的值在left和middle之间，因此可以让right = middle - 1，继续在left和middle - 1之间查找target - 如果中间值小于
target，说明target的值在middle和right之间，因此可以让left = middle + 1，继续在right和middle + 1之间查找target
- 首先声明左边界
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
// 枚举每一行
for (const row of matrix) {
// 在每一行中，使用二分查找搜索是否有数字等于target
if (binarySearch(row, target)) {
return true
}
}
return false
}
// 二分查找
const binarySearch = (row, target) => {
let left = 0 // 左边界
let right = row.length - 1 // 右边界
// 不断搜索直到两个指针相遇
while (left <= right) {
// 每次取中间索引
const middle = (left + right) >> 1
// 查找到中间位置的值
const middleItem = row[middle]
// 如果查找到target，返回true
if (middleItem === target) {
return true
}
// 如果中间值大于target，说明target在左半边
// 将右边界移动到middle - 1
else if (middleItem > target) {
right = middle - 1
}
// 如果中间值小于target，说明target在右半边
// 将左边界移动到middle + 1
else {
left = middle + 1
}
}
return false
}
复杂度分析
- 时间复杂度：
O(mlogn)（m为行数，n为列数）。对一行使用二分查找的时间复杂度为O(logn)，最多需要进行m次二分查找。 - 空间复杂度：
O(1)。
