Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Approach

Java

public class Search2DMatrixII {
    public static void main(String[] args) {
        int[][] matrix = { { 1, 4, 7, 11, 15 }, { 2, 5, 8, 12, 19 }, 
            { 3, 6, 9, 16, 22 }, { 10, 13, 14, 17, 24 },
                { 18, 21, 23, 26, 30 } };
        int target = 5;
        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,4,7,11,15},
                                 {2,5,8,12,19},
                                 {3,6,9,16,22},
                                 {10,13,14,17,24},
                                 {18,21,23,26,30}};
   int  target = 5;
   if(searchMatrix(matrix,target))
     cout<<"true";
   else
     cout<<"false";

   return 0;
}