題目描述

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

對(duì)于有序數(shù)組，我們一般使用二分法進(jìn)行目標(biāo)查找，從而有效減少復(fù)雜度。在該題目中，我們可以將二維數(shù)組的每一行拆開，分別使用二分法。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
       int row = array.size();
       int column = array[0].size(); 
       for (int i = 0; i < row; i++) {
           int low = 0;
           int high = column - 1;
           while (low <= high) {
               int mid = (low + high) / 2;
               if (target == array[i][mid]) return true;
               else if (target > array[i][mid]) low = mid + 1;
               else high = mid - 1;
           }
       }
       return false;
    }
};

不過，在該題目中，除了每一行都從左到右遞增之外，每一列也都從上到下遞增，上面的二分法只利用了第一個(gè)條件。對(duì)于題目所給的條件我們應(yīng)充分利用，從而找出最簡(jiǎn)單的方法。
依舊秉持著“從中間點(diǎn)找一個(gè)數(shù)，再通過判斷決定向哪邊移動(dòng)”的思想，我們可以以左下角或右上角為初始點(diǎn)。假如選取了左下角為第一個(gè)對(duì)比數(shù)，那么當(dāng)該數(shù)大于target時(shí)，應(yīng)向右移，當(dāng)該數(shù)小于target時(shí)，應(yīng)向上移。

從左下角開始查找，代碼如下：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
       int row = array.size();
       int column = array[0].size(); 
       int r = row - 1;
       int c = 0;
       while (r >= 0 && c < column) {
           if (target == array[r][c])
               return true;
           else if (target > array[r][c])
               c++;
           else
               r--;
       }
       return false;
    }
};

從右上角開始查找，代碼如下：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
       int row = array.size();
       int column = array[0].size(); 
       int r = 0;
       int c = column - 1;
       while (r < row && c >= 0) {
           if (target == array[r][c])
               return true;
           else if (target > array[r][c])
               r++;
           else
               c--;
       }
       return false;
    }
};

順便附上一個(gè)本地IDE測(cè)試版：

#include <iostream>
#include <vector>
using namespace std;

//class Solution {
//public:
    bool Find(int target, vector<vector<int> > array) {
       int row = array.size();
       int column = array[0].size(); 
       int r = row - 1;
       int c = 0;
       while (r >= 0 && c < column) {
           if (target == array[r][c])
               return true;
           else if (target > array[r][c])
               c++;
           else
               r--;
       }
       return false;
    }
//};

int main() {
    vector<vector<int> > array2d;
    vector<int> array;
    int row, column, temp, target;
    cin >> row >> column;
    for (int i = 0; i < row; i++) {
        array.clear();
        for (int j = 0; j < column; j++) {
            cin >> temp;
            array.push_back(temp);
        }
        array2d.push_back(array);
    }
    cin >> target;
    if (Find(target, array2d))
        cout << "目標(biāo)存在" << endl;
    else
        cout << "目標(biāo)不存在" << endl;
    return 0; 
}