Search a 2D Matrix Solutions in C++

// Source : https://oj.leetcode.com/problems/search-a-2d-matrix/
// Author : Hao Chen
// Date   : 2014-06-23



class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        return searchMatrix01(matrix, target);
        return searchMatrix02(matrix, target);
    }

    //Just simply convert the 2D matrix to 1D array.
    bool searchMatrix01(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = row>0 ? matrix[0].size() : 0;
        
        int len = row * col;
        int low = 0, high = len -1;
        while (low <= high) {
            
            int mid = low + (high - low) / 2;
            int r = mid / col;
            int c = mid % col;
 
            int n = matrix[r][c];
            if (n == target) return true;
            if (n < target) low = mid+1;
            else high = mid -1;
        }
        return false;
    }



    bool searchMatrix02(vector<vector<int> > &matrix, int target) {
        
        int idx = vertical_binary_search(matrix, target);
        if (idx<0){
            return false;
        }
        
        idx = binary_search(matrix[idx], target);
        
        return (idx < 0 ? false : true);
        
    }
    int vertical_binary_search(vector< vector<int> > v, int key){
        int low = 0;
        int high = v.size()-1;
        while(low <= high){
            int mid = low + (high-low)/2;
            if (v[mid][0] == key){
                return mid;
            }
            if (key < v[mid][0]){
                high = mid - 1;
                continue;
            }
            if (key > v[mid][0]){
                low = mid + 1;
                continue;
            }
        }
        return low-1;        
    }
    
    int binary_search(vector<int> v, int key) {
        int low = 0;
        int high = v.size()-1;
        while(low <= high){
            int mid = low + (high-low)/2;
            if (v[mid] == key){
                return mid;
            }
            if (key < v[mid]){
                high = mid - 1;
                continue;
            }
            if (key > v[mid]){
                low = mid + 1;
                continue;
            }
        }
        return -1;
    }
};

#include <vector>
#include <algorithm>

using std::vector; using std::find; using std::next; using std::prev;

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int m = matrix.size(), n = matrix[0].size(), high = m*n-1;
        for (int low = 0, mid; low < high; )
        {
            mid = (low+high-1) >> 1;
            if (target > matrix[mid/n][mid%n]) low = mid + 1;
            else high = mid;
        }
        return matrix[high/n][high%n] == target;
    }
};

/// Source : https://leetcode.com/problems/search-a-2d-matrix/
/// Author : liuyubobobo
/// Time   : 2019-05-02

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/// Two steps Binary Search
/// Time Complexity: O(logn + logm)
/// Space Complexity: O(m)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        if(!matrix.size() || !matrix[0].size()) return false;
        if(target < matrix[0][0]) return false;

        vector<int> row;
        for(int i = 0; i < matrix.size(); i ++)
            row.push_back(matrix[i][0]);

        int row_index = lower_bound(row.begin(), row.end(), target) - row.begin();
        if(row_index == matrix.size() || matrix[row_index][0] != target)
            row_index --;
//        cout << row_index << endl;

        vector<int>::iterator iter = lower_bound(matrix[row_index].begin(), matrix[row_index].end(), target);
        return iter != matrix[row_index].end() && *iter == target;
    }
};


int main() {

    vector<vector<int>> matrix1 = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 50}
    };
    cout << Solution().searchMatrix(matrix1, 3) << endl;
    // true

    vector<vector<int>> matrix2 = {
            {1}
    };
    cout << Solution().searchMatrix(matrix2, 2) << endl;
    // false

    return 0;
}

/// Source : https://leetcode.com/problems/search-a-2d-matrix/
/// Author : liuyubobobo
/// Time   : 2019-05-02

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/// Think the whole 2d matrix as a 1d array and Binary Search
///
/// Time Complexity: O(log(m*n))
/// Space Complexity: O(1)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        if(!matrix.size() || !matrix[0].size()) return false;

        int m = matrix.size(), n = matrix[0].size();
        int l = 0, r = m * n - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            int x = matrix[mid / n][mid % n];
            if(target == x) return true;
            else if(target < x) r = mid - 1;
            else l = mid + 1;
        }
        return false;
    }
};


int main() {

    vector<vector<int>> matrix1 = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 50}
    };
    cout << Solution().searchMatrix(matrix1, 3) << endl;
    // true

    vector<vector<int>> matrix2 = {
            {1}
    };
    cout << Solution().searchMatrix(matrix2, 2) << endl;
    // false

    return 0;
}