algo-aha

在行列有序的矩阵中查找

• https://leetcode.com/problems/search-a-2d-matrix-ii/
• http://articles.leetcode.com/searching-2d-sorted-matrix-part-ii，或 ctci p410。

按步搜：从行列有序的"中间"位置（右上角或左下角）开始线性搜索。 四分法：值t跟中心点比较，可排除掉左上或右下块，剩下三块子矩阵。 二分法：先在中间行（或中间列或主对角线）上找第一个>=t的数，若它等于t直接返回；否则就是第一个>t的数，可排除掉右下块；再根据它左边相邻数<t排除掉左上块，只剩下两块子矩阵。

bool searchMatrix(vector<vector<int>> &matrix, int target) {
    // 从行列有序的”中间“位置（右上角或左下角）开始线性查找，O(m+n)
    if (matrix.empty()) return false;
    const int R = matrix.size();
    const int C = matrix[0].size();
    int r = 0, c = C - 1;
    while (r < R && c >= 0) {
        if (target == matrix[r][c]) {
            return true;
        } else if (target > matrix[r][c]) {
            r++;
        } else {
            c--;
        }
    }
    return false;
}

行列有序的矩阵中负数的个数

• https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

int countNegatives(vector<vector<int>>& grid) {
    // 从行列有序的"中间"位置（右上角或左下角）开始线性查找，O(m+n)
    if (grid.empty()) return false;
    const int R = grid.size(), C = grid[0].size();
    int r = 0, c = C - 1;
    int ans = 0;
    while (r < R && c >= 0) {
        if (grid[r][c] < 0) { // 类似找0的位置
            c--;
            ans += R - r;
        } else {
            r++;
        }
    }
    return ans;
}