题解 | #二维数组中的查找#

原题

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

[

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

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0 \le val \le 10^90≤val≤109 进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)

思路

每一列都是按照从上到下递增的顺序排序，那么直接用每一列的开始和结尾和target比较，如果target在区间内，就遍历该列，找到target就返回true，否则返回false

代码

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @return bool布尔型
*/
func Find( target int ,  array [][]int ) bool {
    // write code here
    var n = len(array)
    var m = len(array[0])
    for i:=0;i<m;i++{
        if array[0][i]<=target && target<=array[n-1][i]{
            for j:=0;j<n;j++{
                if array[j][i] == target{
                    return true
                }
            }
        }
    }
	return false
}

想法

遍历区间时我是直接暴力遍历的，如果这里优化成二分查找是不是好一点。