题解 | #二维数组中的查找#【js实现】
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
1. 暴力解法，两层for循环遍历
function Find(target, array)
{
// write code here
const row = array.length
const column = array[0].length
for(let i = 0; i < row; i++) {
for(let j = 0; j < column; j++) {
if(array[i][j] === target) {
return true
}
}
}
return false
}
module.exports = {
Find : Find
};
2. 逐行二分，即对二维数组中的每一个元素进行二分查找
function Find(target, array) {
// write code here
const row = array.length;
const column = array[0].length;
for(let i = 0; i < row; i++) {
if(binarySearchTarget(target, array[i])) return true
}
return false
}
// 二分查找target的方法
function binarySearchTarget(target, array) {
let l = 0,
r = array.length - 1;
while (l <= r) {
let m = Math.floor(l + (r - l) / 2);
if (array[m] === target) {
return true;
} else if (array[m] > target) {
// target在左边
r = m - 1;
} else {
// target在右边
l = m + 1;
}
}
return false;
}
module.exports = {
Find: Find,
};
3. 从右上角开始查找
- 二维数组中任意一个数字，左边的数字都比它小，下面的数字都比它大。
function Find(target, array) {
// write code here
if(array.length === 0) return false
const row = array.length
const column = array[0].length
// 从右上角开始找
let i = 0, j = column - 1
while(i <= row - 1 && j >= 0) {
if(target === array[i][j]) {
return true
} else if(target < array[i][j]) {
// 向左查找
j--
} else {
// 向下查找
i++
}
}
return false
}
module.exports = {
Find: Find,
};
