Skip to main content

240. Search a 2D Matrix II

分析

1. 二分法
2. 规律,也有二分的思想

题解

二分法

function searchMatrix(matrix: number[][], target: number): boolean {
for (let i = 0; i < matrix.length; i++) {
const start = matrix[i][0]
const end = matrix[i][matrix[i].length - 1]

if (target < start) {
return false
}
if (target > end) {
continue
}
const findPos = binarySearch(matrix[i], target)
if (findPos !== -1) {
return true
}
}
return false
};

const binarySearch = (arr: number[], target: number) => {
let l = 0, r = arr.length - 1
while (l <= r) {
const mid = l + Math.floor((r - l) / 2)
if (arr[mid] < target) {
l = mid + 1
} else if (arr[mid] > target) {
r = mid - 1
} else {
return mid
}
}
return -1
}

规律法

function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length, n = matrix[0].length
const pos = {
i: 0,
j: n - 1
}

while (pos.i <= m - 1 && pos.j >= 0) {
const current = matrix[pos.i][pos.j]
if (current < target) {
pos.i++
continue
}
if (current > target) {
pos.j--
continue
}
return true
}

return false