1. 概述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

2. 解题

```php <?php class Solution {

/**
 * @param Integer[][] $matrix
 * @param Integer $target
 * @return Boolean
 */
public function searchMatrix($matrix, $target) {
    if (!$matrix) return false;
    // 纵向二分
    $row = -1;
    $top = 0;
    $bottom = count($matrix) - 1;
    while ($top <= $bottom) {
        $verticalMid = $top + floor(($bottom - $top) / 2);
        if ($matrix[$verticalMid][0] == $target) {
            return true;
        } elseif ($matrix[$verticalMid][0] > $target) {
            $bottom = $verticalMid - 1;
        } else {
            if (!isset($matrix[$verticalMid + 1])) {
                $row = $verticalMid;
                break;
            }
            if ($matrix[$verticalMid + 1][0] > $target) {
                $row = $verticalMid;
                break;
            }
            $top = $verticalMid + 1;
        }
    }
    if ($row == -1) {
        return false;
    }
    // 横向二分
    $left = 0;
    $right = count($matrix[$row]) - 1;
    while ($left <= $right) {
        $horizontalMid = $left + floor(($right - $left) / 2);
        if ($matrix[$row][$horizontalMid] == $target) {
            return true;
        } elseif ($matrix[$row][$horizontalMid] < $target) {
            $left = $horizontalMid + 1;
        } else {
            $right = $horizontalMid - 1;
        }
    }
    return false;
}

} $matrix = [ [1,3,5,7], [10,11,16,20], [23,30,34,50] ]; $target = 3; $cls = new Solution(); $r = $cls->searchMatrix($matrix, $target); var_dump($r); ```