Leetcode 74. Search a 2D Matrix

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Treated as a matrix

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

• Treated as an array

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

Reference

1. https://leetcode.com/problems/search-a-2d-matrix/description/