題目網址: https://leetcode.cn/problems/search-a-2d-matrix/

題意: 設計一高效演算法來搜索 m x n matrix 中是否存在整數 target, matrix 滿足以下特性:

  • 每列的元素由左到右按升序排列
  • 每列的第一個元素 > 前一列的最後一個元素

Solution：

想法：利用 Binary Search, matrix 其實就是 1D 已排序的 array, 只是改成用 2D array 表達而已, 故將 matrix 看成 1D array, 然後還原回 2D array 座標來做 Binary Search

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        const int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;

            if (matrix[mid / n][mid % n] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return (left < m * n && matrix[left / n][left % n] == target) ? true : false;
    }
};
  • time：$O(log(mn))$ ➔ Binary Search
  • space：$O(1)$ ➔ 只需常數空間