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 思路

??矩陣從左到右遞增，每行行首大于上一行行尾，相當于可以把矩陣看成多個遞增區(qū)間，采用從頭到尾遍歷整個矩陣的查找方式的話，時間復雜度為O(m * n)；優(yōu)化一下，將整個矩陣拉長成一個遞增序列，再采用二分法，時間復雜度為O[log(m*n)];或者，先縱向做一次二分法，確定目標值可能存在的區(qū)間，即某一行，再對該行做一個二分法，時間復雜度為O(log m + log n) ，與第二種方式的耗時 O[log(m*n)]相等。
??下面會采用最后一種方式來實現(xià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。

3.2 時間復雜度

??先是縱向進行二分搜索，然后橫向進行二分搜索，所以算法的時間復雜度為O(log m + log n)

3.3 空間復雜度

??算法的空間復雜度為O(1)

4 源碼

??注意事項：

對第一列進行二分查找的時候是在第一列中尋找小于目標值的最大值，所以在跳出循環(huán)后的對比中，按照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;
}