分治思想

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

解法

  • 线性搜索：二维矩阵可以用线性搜索的方式来找元素，该矩阵的特点是有序的，每一行的右边元素大于左边元素，每一列的下边元素大于上边元素，因此可以从矩阵的左下角开始搜索，他是最后一行最大的元素，第一列最小的元素，如果目标值大于当前元素，则向右查找，反之向上查找。
  • 二分查找：对每一行都使用二分查找，也能找到某个元素。

参考

https://blog.nowcoder.net/n/3fbe666d7ee443c8b4e957369e960e15?f=comment

https://blog.nowcoder.net/n/f0ecfb6279054551a0669f4e577171f1?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @return bool布尔型
 */
export function Find(target: number, array: number[][]): boolean {
    // write code here
    let i = array.length-1;
    let j = 0;
    
    while (i >= 0 && j < array[0].length) {
        if (array[i][j] > target) {
            // 当前值过大，向上寻找较小的值
            i--;
        }
        else if (array[i][j] < target) {
            // 当前值过小，向右寻找较大的值
            j++;
        }
        else {
            return true;
        }
    }

    return false;
}