目录

• 1 题目
• 2 描述
• 3 思路
  • 3.1 图解
  • 3.2 时间复杂度
  • 3.3 空间复杂度
• 4 源码

1 题目

  搜索m*n矩阵中的目标值（Search a 2D Matrix）

lintcode：题号——28，难度——easy

2 描述

  搜索 m × n矩阵中的值 target ，这个矩阵具有以下特性：每行中的整数从左到右是排序的；每行的第一个数大于上一行的最后一个整数。

  样例1：

输入：矩阵 = [[5]]， target = 2
输出：false
解释：矩阵中没有包含2，返回false。

  样例2：

输入：矩阵 = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]]，target = 3
输出：true
解释：矩阵中包含3，返回true。

3 思路

  矩阵从左到右递增，每行行首大于上一行行尾，相当于可以把矩阵看成多个递增区间，采用从头到尾遍历整个矩阵的查找方式的话，时间复杂度为O(m * n)；优化一下，将整个矩阵拉长成一个递增序列，再采用二分法，时间复杂度为O[log(m*n)];或者，先纵向做一次二分法，确定目标值可能存在的区间，即某一行，再对该行做一个二分法，时间复杂度为O(log m + log n) ，与第二种方式的耗时 O[log(m*n)]相等。
  下面会采用最后一种方式来实现，二分法依然可以套用经典二分搜索^[1]的代码模版。

1. 在矩阵第一列中进行二分搜索，找到小于目标值的最大行首元素，目标值只可能在该行中；
2. 对目标行进行二分搜索，即可确定是否存在该值。

  其实还有一种思维上更简单的方式，类似走楼梯，从左下角为起点，如果当前值大于目标值，则向上走一格；如果当前值小于目标值，则向右走一格，直到找到目标值，或者走出矩阵范围为止。

走楼梯算法在代码上更精简，代码一起在结尾给出，但该算法时间复杂度为O(m+n)，比O(log m + log n)耗时更长。

3.1 图解

输入：矩阵 = [
[01, 03, 05, 07，09],
[10, 11, 16, 20，21],
[23, 30, 34, 50，57],
[71, 80, 86, 87，99]]，target = 20
输出：true
解释：矩阵中包含20，返回true。

graph TD X['01, 03, 05, 07, 09'<br/>'10, 11, 16, 20, 21'<br/>'23, 30, 34, 50, 57'<br/>'71, 80, 86, 87, 99'] X -- 首列 --> A['01, -, -, -, -'<br/>'10, -, -, -, -'<br/>'23, -, -, -, -'<br/>'71, -, -, -, -'] A -- 二分法找到小于20的最大值 --> B['-, -, -, -, -'<br/>'10, -, -, -, -'<br/>'-, -, -, -, -'<br/>'-, -, -, -, -'] B -- 取出该行 --> C['-, -, -, -, -'<br/>'10, 11, 16, 20, 21'<br/>'-, -, -, -, -'<br/>'-, -, -, -, -'] C -- 再二分法搜索目标值 --> D['-, -, -, -, -'<br/>'-, -, -, 20, -'<br/>'-, -, -, -, -'<br/>'-, -, -, -, -'] D -- 搜索成功 --> F[存在]

3.2 时间复杂度

  先是纵向进行二分搜索，然后横向进行二分搜索，所以算法的时间复杂度为O(log m + log n)

3.3 空间复杂度

  算法的空间复杂度为O(1)

4 源码

  注意事项：

对第一列进行二分查找的时候是在第一列中寻找小于目标值的最大值，所以在跳出循环后的对比中，按照target相对于start～end的位置关系，可以分为三种情况去处理。

  两次二分搜索算法，C++版本：

/**
* @param matrix: 矩阵
* @param target: 目标值
* @return: 返回true表示目标值在矩阵中，否则返回false
*/
bool searchMatrix(vector<vector<int>> &matrix, int target) {
    // write your code here
    if (matrix.size() == 0 || matrix.front().size() == 0)
    {
        return false;
    }

    int start = 0;
    int end = matrix.size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (matrix.at(mid).front() == target)
        {
            return true;
        }
        if (matrix.at(mid).front() < target)
        {
            start = mid;
        }
        if (matrix.at(mid).front() > target)
        {
            end = mid;
        }
    }

    if (matrix.at(start).front() > target)
    {
        return false;
    }
    if (matrix.at(end).front() > target)
    {
        return binarySearch(matrix, start, target);
    }
    else
    {
        return binarySearch(matrix, end, target);
    }
}

bool binarySearch(vector<vector<int>> & matrix, int row, int target)
{
    int start = 0;
    int end = matrix.at(row).size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (matrix.at(row).at(mid) == target)
        {
            return mid;
        }
        if (matrix.at(row).at(mid) < target)
        {
            start = mid;
        }
        if (matrix.at(row).at(mid) > target)
        {
            end = mid;
        }
    }

    if (matrix.at(row).at(start) == target)
    {
        return true;
    }
    if (matrix.at(row).at(end) == target)
    {
        return true;
    }

    return false;
}

附加：
  走楼梯算法，C++版本：

bool searchMatrix(vector<vector<int>> &matrix, int target) {
    // write your code here
    if (matrix.empty())
    {
        return false;
    }
    if (matrix.front().empty())
    {
        return false;
    }
    
    // 走楼梯法
    int row = matrix.size() - 1;
    int col = 0;
    int curValue = 0;
    while (row >= 0 && col <= matrix.front().size() - 1)
    {
        curValue = matrix.at(row).at(col); // 起点左下角
        if (curValue > target)
        {
            row--; // 如果目标元素不存在，则最后会走出矩阵范围
        }
        else if (curValue < target)
        {
            col++; // 如果目标元素不存在，则最后会走出矩阵范围
        }
        else
        {
            return true;
        }
    }
    
    return false;
}

---

1. 经典二分搜索：https://blog.csdn.net/SeeDoubleU/article/details/118271548 ↩︎