Leetcode Search a 2D Matrix 搜索二维表

Search a 2D Matrix

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.

  这道题的解法倒是很多的，网上也有不少分析的。

  比如LeetCode论坛上有分析非常仔细的，不过他好像推荐的是个O(n+m)的时间效率，这次也是个例外了，他的分析和例子都不好。

  因为这道题的最优时间效率应该是O(lgm +lgn); m,n 代表行和列数，而且也没有那么复杂，不过就是考二分法的运用，能够灵活运用了做这道题不是难事，本人一次性通过。

  这里是使用二分法，先列二分，然后行二分，看似复杂，其实是很简单的程序。不用看Leetcode上的那么长编大论的分析。

  下面是我的程序，看起来长，其实结构很清晰，很好理解的程序。

  	const static int FOUND = -2;
  	const static int NOT_FOUND = -1;
  
  	bool searchMatrix(vector
      
        > &matrix, int target) 
  	{
  		int found_mark = searchRow(matrix, 0, matrix.size()-1, target);
  		if (found_mark == NOT_FOUND) return false;
  		if (found_mark == FOUND) return true;
  
  		found_mark = searchCol(matrix, found_mark, 0, matrix[0].size()-1, target);
  
  		if (found_mark == NOT_FOUND) return false;
  		return true;
  	}
  
  	int searchRow(vector
       
         > &m, int low, int up, int tar) { //up = -1的时候也是等于NOT_FOUND,所以设NOT_FOUND=-1 if (low > up) return up; int mid = low + ((up - low)>>1); if (tar < m[mid][0]) { return searchRow(m, low, mid-1, tar); } else if (m[mid][0] < tar) { return searchRow(m, mid+1, up, tar); } else return FOUND; } int searchCol(vector
        
          > &m, int row, int left, int right, int tar) { if (left > right) return NOT_FOUND; int mid = left + ((right - left)>>1); if (tar < m[row][mid]) { return searchCol(m, row, left, mid-1, tar); } else if(m[row][mid] < tar) { return searchCol(m, row, mid+1, right, tar); } else return FOUND; }
        
       
      

  
  
  

  下面也看看Leetcode上的程序，也是很简单的，不过他说这个也许是面试官需要的答案？那我就怀疑了，O(lgn + lgm)比O(n+m)提高了一个档次的时间复杂度啊，当然是二分法好啦。

  //属于上下行，左右列夹并追踪目标的方法，复杂度O(n+m)
  	bool searchMatrix2(vector
      
        > &matrix, int target) {
  		int m(matrix.size()-1), n(matrix[0].size()), k(0);
  		while(m>=0 && k
       
        target) --m; else ++k; } return false; }