在二维数组中查找指定值 #

一.数组 #

数组是一种最简单的数据结构，在内存中占据一块连续的存储结构，可以通过数组下标进行访问。对比链表，其具有访问速度快，时间效率 高的特点。但是数组需要预先在内存中分配存储空间，因此数组的空间效率不是很好，经常会有空间没有得到充分的利用。

二.二维数组中的查找 #

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 例如，有如下数组a，需要在里面寻找7。

1,3,6,7
3,6,8,10
5,9,10,12

很多人，按照惯性思维会直接从下标0开始进行比较，将a[0][0]与7进行比较，a[0][0]小于7，所以可能的值在左下方和右上方，继续比较a[1][1]，a[1][1]小于7，得到7可能存在于左下方和右上方。每次比较都会出现两个可能的区域左下方和右上方，这样看问题会变得越来越复杂。

所以不妨换一个角度，从右上角出发，每次比较右上角的数字，来缩小比较范围，例如我们要在a中寻找5，首先将7与5比较，7大于5，所以7所在的列不可能存在5。所以踢出当前列。在将6与5比较，6大于5，再踢出6所在的列。继续比较3和5，因为3小于5，所以踢出3所在的行。这样每比较一次，会缩小查找的范围，直到找到5。

代码：

/**
 * 在二维数组中查找指定值
 * @param arr 二维数组
 * @param value 需要查找的值
 * @returns 如果存在返回索引值, 不存在返回{i: -1, j: -1}
 */
const includes = (arr: number[][], value: number): boolean => {
    // 检查数组长度
    if (arr.length === 0) {
        return false;
    }
    if (arr[0].length === 0) {
        return false;
    }
    // 从数组右上角进行比较
    let i = 0, j = arr[0].length - 1;
    while(i < arr.length && j > 0) {
        if (arr[i][j] === value) {
            return true;
        }
        if (arr[i][j] < value) {
            i++;
        }
        if (arr[i][j] > value) {
            j--;
        }
    }
    return false;
};

测试:

const arr1: number[][] = [[]];
const arr2: number[][] = [[1, 3, 5, 7], [3, 6, 8, 10], [5, 9, 10, 12], [7, 12, 14, 20]];
const arr3: number[][] = [[1, 3, 5, 7], [3, 6, 8, 10]];
console.log(includes(arr1, 0)); // false
console.log(includes(arr2, -1)); // false
console.log(includes(arr2, 7)); // true
console.log(includes(arr2, 5)); // true
console.log(includes(arr2, 4)); // false
console.log(includes(arr3, -1)); // false
console.log(includes(arr3, 7)); // true
console.log(includes(arr3, 5)); // true
console.log(includes(arr3, 4)); // false

同样我们也可以从左下角进行出发，当比较的数字大于目标值时，踢出当前行，小于目标值时踢出当前列，以此来缩小查找范围。

github地址。

（完）