前端常见算法面试题之 - 二维数组中的查找[JavaScript解法]

╰+哭是因爲堅強的太久メ 2022-05-15 14:15 168阅读 0赞

### 前端常见算法面试题之 - 二维数组中的查找\[JavaScript解法\] ###

*  题目描述
 *  输入输出分析
 *  实现思路
 *  代码实现

# 题目描述 #

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

# 输入输出分析 #

每当拿到一个算法题的时候，不要脑子中稍微有点思路后，就开始写代码。而是先把题目中规定的参数搞清楚，然后把参数的例子写出来。

本题两个参数举例：

1.  递增二维数组

1   2   8   9
    2   4   9   12
    4   7   10  13
    6   8   11  15

`注意` 题目只说每一行是递增的，没有说增幅是多少，不要以为增幅是1。同时也没有说行数和列数相等

1.  要查找的整数

比如：7、5、0、16

对应的输出结果：true、false、false、false

# 实现思路 #

1.  暴力遍历法

面试官要的肯定不是这个结果，直接跳过

1.  二分查找法

仔细看这个二维数组最右上角这个数。它所在的行，左面的数字比它小；所在的列，下面的数字比它大：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70]

如果要查询的数字比9大，那么9所在的行就不用在比较了，接下来只需要比较9下面的所有行

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70 1]

如果要查询的数字比9小，那么9所在的列就不用在比较了，接下来只需要比较9左面的所有列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70 2]

通过这一次的比较，我们就能得到一个新的范围（矩形）。接着继续利用新范围右上角的数字，与要查找的整数进行比较。比较过后，又能得到一个新的进一步缩小的范围（矩形）。如此往复，直到找到目标整数，或者没有找到。

> 每一次比较的过程，比较类似二分查找

比如要查找数字7，那么查找的路径如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70 3]

每一步都是通过比较所在行左面数字和所在列下面数字的大小，确定下一步指针的移动方向。

同理，我们还可以从矩形的左下角的数字开始比较

最后，别忘了要把特殊情况考虑进去，比如参数的特殊值

# 代码实现 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70]: /images/20220503/339dd7f3f8d440268d8e5520f564dbe5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70 1]: /images/20220503/bff6cb5fe6aa46399def57d6f1a6bd73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70 2]: /images/20220503/c98c9ab6c63a4a279f5f73c398be1431.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQzOTc0MQ_size_16_color_FFFFFF_t_70 3]: /images/20220503/4ef4b8e3ce95478791bff78f109dc05c.png