Leetcode_c++: Search a 2D Matrix (074)

タイトル
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.
アルゴリズム#アルゴリズム#
複雑度:O(lg(nm))二分法によりtargetが数行目に現れる可能性があることを決定し、二分法によりこの行にtargetが現れる可能性がある位置を決定する.時間複雑度O(logn+logm)

class Solution {  
public:  
    bool searchMatrix(vector<vector<int> > &matrix, int target) {  
        int left = 0;  
        int right = matrix.size()-1;  
        if(left != right)  
        {  
            while(left<=right)  
            {  
                int middle = left + (right-left)/2;  
                if(matrix[middle][0] < target)  
                {  
                    left = middle+1;  
                }  
                else if(matrix[middle][0] > target)  
                {  
                    right = middle-1;  
                }  
                else  
                {  
                    return true;  
                }  
            }  
        }  
        if(right == -1)  
        {  
            return false;  
        }  
        else  
        {  
            int row = right;  
            int left = 0;  
            int right = matrix[row].size()-1;  
            while(left<=right)  
            {  
                int middle = left + (right-left)/2;  
                if(matrix[row][middle] < target)  
                {  
                    left = middle+1;  
                }  
                else if(matrix[row][middle] > target)  
                {  
                    right = middle-1;  
                }  
                else  
                {  
                    return true;  
                }  
            }  
            return false;  
        }  

    }  
};  

//         
class Solution {
public:
  bool searchMatrix(const vector<vector<int> > &matrix, int target){
    if (matrix.empty()) return false;
    int m = matrix.size(), n = matrix.front().size();
    int begin = 0, end = m * n, middle, row, col;


    while(begin < end){
      middle = begin + (end - begin) / 2;
      int row = middle / n;
      int col = middle % n;
      if(matrix[row][col] == target) return true;
      else if(matrix[row][col] < target) begin = middle + 1;
      else end = middle;
    }
    return false;
  }
};

アルゴリズム#アルゴリズム#
右上の要素からループを開始し、各ループでtargetと等しい場合はtrueを返します.より小さい場合は行が下に移動します.より大きい場合は列を左に移動します.時間複雑度m+n

class Solution {  
public:  
    bool searchMatrix(vector<vector<int> > &matrix, int target) {  
        int i =matrix.size()-1; int j=0;  
        int n = matrix.size(); int m = matrix[0].size();  
        while(i>=0&&jif(matrix[i][j]==target)  
            {  
                return true;  
            }  
            else if(matrix[i][j]else  
            {  
                i--;  
            }  
        }  
        return false;  
    }