剑指 Offer 04. 二维数组中的查找

题目链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

本文基于JavaScript语言的解法：一、接口方法解决　　二、二分搜索树解法【巧妙】

一、接口方法解决

Array.ptototype.includes() : 用来判断一个数组是否包含一个指定的值，根据情况，如果包含则返回 true，否则返回 false。

 1 /**
 2  * @param {number[][]} matrix
 3  * @param {number} target
 4  * @return {boolean}
 5  */
 6 var findNumberIn2DArray = function(matrix, target) {
 7     for(let i = 0; i < matrix.length; i++) {
 8       if(matrix[i].includes(target)) return true;
 9     }
10     return false;
11 };

 二、二分搜索树解法【巧妙】

题目描述的二维数组的规则：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

稍微将左图转一下-->右图：就是一棵左小右大的二分搜索树了。

 1 /**
 2  * @param {number[][]} matrix
 3  * @param {number} target
 4  * @return {boolean}
 5  */
 6 var findNumberIn2DArray = function (matrix, target) {
 7   if(matrix == null || matrix[0] == null) return false;
 8   let length = matrix.length;
 9   let i = 0;
10   let j = matrix[0].length - 1;
11   while(i < length && j >= 0){
12     if(target == matrix[i][j]) return true;
13     if(target > matrix[i][j]) i++;
14     else j--;
15   }
16   return false;
17 };