二维数组中的查找

发表于2020-05-19更新于2020-05-19

在线测评地址：牛客网

题目描述

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

限制

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M 热度指数：1802254

本题知识点： 查找 数组

思路

采用右上角或左下角开始遍历。我以右上角为例，如果比目标数大，去除所在列，如果比目标数小，去除所在行，直到行或列超出范围，仍然没有找到目标数，则为false，反之为true。

编程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Find(target, array)
{
    var x_max = array.length
    var x = 0
    var y = array[0].length - 1
    while (x < x_max && y >= 0) {
        if (array[x][y] === target) {
            return true
        } else if (array[x][y] < target) {
            x++
        } else {
            y--
        }
    }
    return false
}