74. 搜索二维矩阵

题意：

解题思路：

思路：
1.双指针
2.(二分) O(logn)
    2.1 把整个矩阵，按照行展开成一个数组，这个数组是单调递增，通过二分搜索即可
    2.2 二分时可以通过整除和取模运算得到二维数组的坐标。
    m = count(matrix);
  n = count(matrix[0]);
    行 = mid / n，列 = mid % n

PHP代码实现：

class Solution {
    /**
     * @param Integer[][] $matrix
     * @param Integer $target
     * @return Boolean
     */
    function searchMatrix($matrix, $target) {
        $n = count($matrix);
        $m = count($matrix[0]);
        $x = $n - 1; $y = 0;
        $count = 0;
        while ($x >= 0 && $y < $m) {
            if ($matrix[$x][$y] < $target) {
                $y++;
            } else if ($matrix[$x][$y] > $target) {
                $x--;
            } else {
                $count++;
                $x--;$y++;
            }
        }
        return $ocunt;
    }
    function searchMatrixBs($matrix, $target) {
        $m = count($matrix);
        $n = count($matrix[0]);
        $low = 0; $high = $m * $n - 1;
        while ($low <= $high) {
            $mid = $low + floor(($high - $low) >> 1);
            //$mid / $n = 行，$mid % $n = 列
            $r = $mid / $n;
            $c = $mid % $n;
            if ($target < $matrix[$r][$c]) $high = $mid - 1;
            else if ($target > $matrix[$r][$c]) $low = $mid + 1;
            else return true;
        }
        return false;
    }
}

GO代码实现：

func searchMatrix(matrix [][]int, target int) bool {
    searchMatrixBs(matrix, target)
    if len(matrix) == 0 {
        return false
    }
    row := len(matrix)
    col := len(matrix[0])
    i, j := row - 1, 0
    for i >= 0 && j < col {
        if matrix[i][j] == target {
            return true
        } else if matrix[i][j] > target {
            i--
        } else {
            j++
        }
    }
    return false
}
func searchMatrixBs(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    if m == 0 || n == 0 {
        return false
    }
    low, high := 0, m * n -1
    for low <= high {
        mid := (low + high) >> 1
        r := mid / n
        c := mid % n
        if target == matrix[r][c] {
            return true
        } else if target < matrix[r][c] {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return false
}