Problem :

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1 :

**Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true**

Example 2 :

**Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: fals**

核心思維 :

1. 設定矩陣行列數(r, c)、左右指標(left, right)和中間值mid
2. 設定row = mid的列數m和column = mid的行數
3. 進行二分搜尋法持續至找出目標值

• 當中間值與目標值相同，回傳true
• 當中間值大於目標物，調整右指標
• 當中間值小於目標值，調整左指標

4. 二分搜尋法的搜尋結束後若未找到目標值，回傳false

程式碼 :

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //設定r = 矩陣列數, c = 矩陣行數
        int r = matrix.size();
        int c = matrix[0].size();
        //設定左指標 = 0, 右指標 = 陣列尾端
        int left = 0;
        int right = r * c - 1;
        while(left <= right){
            //設定中間值
            int mid = left + (right - left) / 2;
            //設定row = mid的列數m, 設定column = mid的行數
            int row = mid / c;
            int column = mid % c;
            //當中間值與目標值相同，回傳true
            if(matrix[row][column] == target){
                return true;
            }
            //當中間值大於目標物，調整右指標
            else if(target < matrix[row][column]){
                right = mid - 1;
            }
            //當中間值小於目標值，調整左指標 
            else{
                left = mid + 1;
            }
        }
        //若未找到目標值，回傳false
        return false;
    }
};

結論 :

這裡利用二分搜尋法來處理二維陣列的問題，首先設定矩陣行列數和左右指標，接著找出中間值並利用目標值的大小來決定接下來尋找目標值得方向，重複利用相同的步驟縮小搜尋範圍，持續至找到並回傳true，若發現目標值不在範圍內，便回傳false，使用二元搜尋法處理陣列問題，過程中活用陣列的設定和二元搜尋法。