Leetcode 74. Search a 2D Matrix

Tyan

发布于 2019-05-26 08:47:27

3300

发布于 2019-05-26 08:47:27

文章被收录于专栏：SnailTyan

文章作者：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;
    }
};