74. Search a 2D Matrix （二分查找）

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.

思路1：

这道题目是查找矩阵中的数。由于是排好序的，直接一个一个搜复杂度很高，所以从左下角开始，大于这个数的就右移一列，小于这个数就上移一行。

 var searchMatrix = function(matrix, target) {
            if (matrix.length === 0) {
                return false;
            }
            var i = matrix.length - 1;
            console.log(i);
            for (var j = 0; i >= 0 && j<matrix[i].length;) {
                console.log(i)
                if (matrix[i][j] > target) {
                    i--;
                } else if (matrix[i][j] < target) {
                    j++;
                } else {
                    return true;
                }
            }

            return false;
        };

思路2：

二分搜索
可以在第一列上先用一次二分查找法找到目标值所在的行的位置，然后在该行上再用一次二分查找法来找是否存在目标值
艘一次也可以：
按S型遍历该二维数组，可以得到一个有序的一维数组，那么我们只需要用一次二分查找法，而关键就在于坐标的转换，如何把二维坐标和一维坐标转换是关键点，把一个长度为n的一维数组转化为mn的二维数组(mn = n)后，那么原一维数组中下标为i的元素将出现在二维数组中的[i/n][i%n]的位置，有了这一点，代码很好写出来了：