Search a 2D Matrix

search in a 2D array.png

===================== 解題思路 =====================

同樣以 BS 的做法來找 搜索範圍是 0 ~ mn -1 (總共就 mn 個數值), 設定 left right 跟 mid 每次減半搜索範圍, 但題目給的是一個 2D 陣列, 所以要將行與列來做一個轉換拿到真正在 2D 陣列裡的位置 同樣這類型題目都採用 while(left + 1 < right) 的做法避免死循環, 所以在結束 loop 以後要對 left 跟 right 各自檢查一次是否符合題目需要

===================== C++ code ====================

<pre><code>
class Solution {

public:

/**
 * @param matrix, a list of lists of integers
 * @param target, an integer
 * @return a boolean, indicate whether matrix contains target
 */
bool searchMatrix(vector<vector<int> > &matrix, int target) {
    // write your code here
    if(matrix.size() == 0) return false;
    int m = matrix.size(), n = matrix[0].size();
    int left = 0, right = m * n - 1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(matrix[mid / n][mid % n] == target) return true;
        else if(matrix[mid / n][mid % n] > target) right = mid;
        else left = mid;
    }
    if(matrix[left / n][left % n] == target) return true; 
    if(matrix[right / n][right % n] == target) return true;
    return false;
}

};
<code><pre>