SearchA2DMatrix [source code]

public class SearchA2DMatrix {
static
/******************************************************************************/
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;
        int R = matrix.length, C = matrix[0].length;
        int lo = 0, hi = R - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[mid][0] == target)
                return true;
            else if (target < matrix[mid][0])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        if (lo == 0)
            return false;
        int row_idx = lo - 1;
        lo = 0;
        hi = C - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[row_idx][mid] == target)
                return true;
            else if (target < matrix[row_idx][mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return false;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SearchA2DMatrix.Solution tester = new SearchA2DMatrix.Solution();
        int[][][] inputs = {
            {{1}}, {{0}}, {{0}},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[][] matrix = inputs[3 * i];
            int target = inputs[3 * i + 1][0][0];
            boolean ans = inputs[3 * i + 2][0][0] > 0;
            System.out.println (Printer.separator ());
            boolean output = tester.searchMatrix (matrix, target);
            System.out.printf ("%s and %d -> %s, expected: %b\n", 
                Matrix.printMatrix (matrix), target, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

因为是sorted, 所以binary search很明显; 这里注意一个问题, 假如我们第一个pass, 只搜所有row的head, 够吗? 一个uncertainty是, 万一是9这样的呢? 但是立刻排除uncertainty: 不对, 无法排除, 这个题目本身返回的是boolean, 所以实际上是可能出现9这样的东西的; 我一开始以为target肯定存在; 如果是那种情况, 一般就是要你返回index了;

again, 仔细读题目, 没说一定存在, 所以就不要自己乱假设;

不对啊, 可以用这个帮助分析啊, 比如9, 9因为 < 10, 所以直接search row heads, 得到的肯定是第一行(insertion position), 然后直接在第一行再搜就行了, 搜不到就是不存在, 反正只要存在, 就不可能在第二行, 你在第一行找不到就是找不到了;

顺利做完, 速度是12ms (16%), 好像有点丢人;

反正就用Sedgwick写法的binary search, 搜出来lo就是insertion position, 这个很熟悉了; 注意, 可能得到的是0, 这个在这个题目的情形下, 直接就可以return FALSE了: insert at 0, 意思就是太小了, 出界;

没有editorial;

@vaputa said in Don't treat it as a 2D matrix, just treat it as a sorted list:

Use binary search.

n m matrix convert to an array => matrix[x][y] => a[x m + y]

an array convert to n * m matrix => a[x] =>matrix[x / m][x % m];

class Solution {  
public:  
    bool searchMatrix(vector<vector<int> > &matrix, int target) {  
        int n = matrix.size();  
        int m = matrix[0].size();  
        int l = 0, r = m * n - 1;  
        while (l != r){  
            int mid = (l + r - 1) >> 1;  
            if (matrix[mid / m][mid % m] < target)  
                l = mid + 1;  
            else   
                r = mid;  
        }  
        return matrix[r / m][r % m] == target;  
    }  
};

想法有点意思, 确实, 直接转化成1D index就行了; 但是这个算法有一个毛病: 复杂度不利: O(log(RC)), 而我的方法是O(logR + logC); 不对啊, 这两个复杂度实际上是一样的? 自己脑子糊涂了;

@zhongjp058 said in Don't treat it as a 2D matrix, just treat it as a sorted list:

m * n may overflow for large m and n. I think it is better to binary search by row first, then binary search by column. The time complexity is the same but this avoids multiplication overflow.

@dragonmigo said in Don't treat it as a 2D matrix, just treat it as a sorted list:

There is actually a third reason why this method is not the optimal: Cache hit rate. This method is not as cache friendly as doing the row->column 2 binary search way.

角度很有意思, 不过很玄学, 而且未必正确;

@cqbaoyi said in Don't treat it as a 2D matrix, just treat it as a sorted list:

@dragonmigo
It is truly an interesting perspective. However, I think the cache hit rate of this method is not worse than that of row->column binary search method.
The reason is that C++ is row-major ordering. Both methods cause possibly multiple cache misses. They both make memory access jump multiple times. I do not see one has a better spatial locality than the other.
Please correct me if I am wrong.

@yuanliay said in Don't treat it as a 2D matrix, just treat it as a sorted list:

There are two main reasons why treating the matrix as a sorted array is a bad idea, considering that it doesn't bring any improvement on time complexity : 1. as zhongjp058 mentioned, m*n may cause overflow; 2. it uses multiple expensive operations such as / and %

这个是实话, 好好的非要用除法干什么;

@StefanPochmann said in Don't treat it as a 2D matrix, just treat it as a sorted list:

@JadenPan I don't think it'll happen for "rows", either. As far as I know, accessing some memory location does read more into the cache than just that location, but it's something like 64 bytes, not the "array row". If it did read an entire (long) array row, that would probably be slower, because most of it isn't going to get used.

So at the very end of the binary search, when the steps are smaller than 64 bytes, you might benefit from caching. Before that, it's irrelevant. Furthermore, the "treat it as a sorted list" solution will also benefit from that!

这个是关于cache的另外一个讨论, 这个感觉讲的有道理一些;

@goodsign said in Binary search on an ordered matrix:

Cannot pass the test, you missed one line:

if (matrix.length == 0 || matrix[0].length == 0) return false;

base case写多点没坏处好吧;

@summer.ji.5 said in Java clear solution:

The basic idea is from right corner, if the current number greater than target col - 1 in same row, else if the current number less than target, row + 1 in same column, finally if they are same, we find it, and return return.

public boolean searchMatrix(int[][] matrix, int target) {  
    int i = 0, j = matrix[0].length - 1;  
    while (i < matrix.length && j >= 0) {  
            if (matrix[i][j] == target) {  
                return true;  
            } else if (matrix[i][j] > target) {  
                j--;  
            } else {  
                i++;  
            }  
        }  

    return false;  
}

看起来像是binary search, 实际上不是, 这个是一个O(M+N)的算法;

@shiyaoeating said in Java clear solution:

@abhisheak It's not O(mn), the worst case is O(m + n). You don't need to iterate through each column for each row.

@abhisheak said in Java clear solution:

This is a 2 pointer method and not binary search. Worst case performance is O(mn) which is basically same as looking at each element one by one.

We are not taking advantage of the sorting already done.
Using binary search, we can finish in O(log(mn)).

这个说O(MN)的是不对的, 明显是没有理解这个算法实际的操作;

submission基本波动和老的代码;

Problem Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[  
  [1,   3,  5,  7],  
  [10, 11, 16, 20],  
  [23, 30, 34, 50]  
]

Given target = 3, return true.

Difficulty:Medium
Total Accepted:149.2K
Total Submissions:428.7K
Contributor:LeetCode
Related Topics
arraybinary search
Similar Questions
Search a 2D Matrix II