LeetCode 74:Search a 2D Matrix

Write an efficient algorithm that searches for a value in anmxnmatrix. 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]
  ]
  

  Giventarget=3, returntrue.

  Subscribeto see which companies asked this question

   class Solution {
   public:
  	 bool searchMatrix(vector>& matrix, int target) {
  		 if (matrix.size() == 0)     return false;
  		 if (matrix[0][0] > target)  return false;
  		 int r = matrix.size(), c = matrix[0].size(); //r,c分別為矩陣matrix的行數和列數
  		 int low = 0, high = r-1;
  
  		 //在所有行中利用二分查找target所在的行
  		while(low <= high)
  		 {
  			 int mid = low + (high-low) / 2;
  			 if (matrix[mid][0] == target)
  				 return true;
  			 else if (matrix[mid][0] < target)
  				 low = mid + 1;
  			 else
  				 high = mid - 1;
  		 }
  
  		//在target所在行中利用二分查找target
  		int low1 = 0, high1 = c - 1;
  		int k = 0;
  		while (low1 <= high1)
  		{
  			int mid1 = low1 + (high1 - low1)/2;
  			if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
  				return true;
  			else if (matrix[low-1][mid1] < target)
  				low1 = mid1 + 1;
  			else
  				high1 = mid1 - 1;
  
  			k = mid1;
  		}
  		
  		if (matrix[low-1][k] == target) 
  			return true;
  		else
  			return false;
  	 }
   };

  
  
  

  測試代碼：

  #include
  #include
  #include
  using namespace std;
  
   class Solution {
   public:
  	 bool searchMatrix(vector>& matrix, int target) {
  		 if (matrix.size() == 0)     return false;
  		 if (matrix[0][0] > target)  return false;
  		 int r = matrix.size(), c = matrix[0].size(); //r,c分別為矩陣matrix的行數和列數
  		 int low = 0, high = r-1;
  
  		 //在所有行中利用二分查找target所在的行
  		while(low <= high)
  		 {
  			 int mid = low + (high-low) / 2;
  			 if (matrix[mid][0] == target)
  				 return true;
  			 else if (matrix[mid][0] < target)
  				 low = mid + 1;
  			 else
  				 high = mid - 1;
  		 }
  
  		//在target所在行中利用二分查找target
  		int low1 = 0, high1 = c - 1;
  		int k = 0;
  		while (low1 <= high1)
  		{
  			int mid1 = low1 + (high1 - low1)/2;
  			if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
  				return true;
  			else if (matrix[low-1][mid1] < target)
  				low1 = mid1 + 1;
  			else
  				high1 = mid1 - 1;
  
  			k = mid1;
  		}
  		
  		if (matrix[low-1][k] == target) 
  			return true;
  		else
  			return false;
  	 }
   };
  
  
  int main()
  {
  	Solution s;
  	vector> nums1 = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, {23,30,34,50} };
  	bool  t = s.searchMatrix(nums1, 11);
  	cout << t <