Search a 2D Matrix

Write an efficient algorithm that searches for a value in an mXn 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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Approach

Java

public class Search2DMatrix {
    public static void main(String[] args) {
        int[][] matrix = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 },
         { 23, 30, 34, 60 } };

        int target = 3;
        System.out.println(searchMatrix(matrix, target));
    }

    static boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            if (searchElement(matrix[i], target))
                return true;
        }
        return false;
    }

    private static boolean searchElement(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > target)
                high = mid - 1;
            else if (arr[mid] < target) {
                low = mid + 1;
            } else
                return true;

        }
        return false;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

bool searchMatrix(vector<vector<int>> &matrix, int target)
{
    for (int i = 0; i < matrix.size(); i++)
    {
        if (binary_search(matrix[i].begin(), matrix[i].end(), target))
            return true;
    }
    return false;
}

int main()
{
    vector<vector<int>> matrix = {{1, 3, 5, 7},
                                 {10, 11, 16, 20},
                                 {23, 30, 34, 60}};

    int target = 3;
    if (searchMatrix(matrix, target))
        cout << "true";
    else
        cout << "false";

    return 0;
}