[LeetCode] Search a 2D Matrix, Solution

ゞ浴缸里的玫瑰 2021-12-17 09:57 201阅读 0赞

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`.

[» Solve this problem][Solve this problem]  
  
\[Thoughts\]  
做两次二分就好了，首先二分第一列，找出target所在的行，然后二分该行。  
  
\[Code\]

1:       bool searchMatrix(vector<vector<int> > &matrix, int target) {  
    2:            int row = matrix.size();  
    3:            if(row ==0) return false;  
    4:            int col = matrix[0].size();  
    5:            if(col ==0) return false;      
    6:            if(target< matrix[0][0]) return false;  
    7:            int start = 0, end = row-1;  
    8:            while(start<= end)  
    9:            {  
    10:                 int mid = (start+end)/2;  
    11:                 if(matrix[mid][0] == target)  
    12:                      return true;  
    13:                 else if(matrix[mid][0] < target)  
    14:                      start = mid+1;  
    15:                 else  
    16:                      end = mid-1;  
    17:            }  
    18:            int targetRow = end;  
    19:            start =0;  
    20:            end = col-1;  
    21:            while(start <=end)  
    22:            {  
    23:                 int mid = (start+end)/2;  
    24:                 if(matrix[targetRow][mid] == target)  
    25:                      return true;  
    26:                 else if(matrix[targetRow][mid] < target)  
    27:                      start = mid+1;  
    28:                 else  
    29:                      end = mid-1;  
    30:            }  
    31:            return false;  
    32:       }

注意，  
二分的条件应该是（start<=end）， 而不是（start<end）。

转载于:https://www.cnblogs.com/codingtmd/archive/2013/03/18/5078891.html

[Solve this problem]: http://leetcode.com/onlinejudge#