Search a 2D Matrix II (Sorted Matrix)

[Question] : Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This 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

Why Binary Search is not useful for searching in unsorted arrays?

The basic condition to apply Binary Search anywhere in any algorithm is that the search space should be sorted. To perform a Binary search in the 2D array, the array needs to be sorted. Here is an unsorted 2D array is given, so applying Binary Search in an unsorted array is not possible. To apply Binary Search first the 2D array needs to be sorted in any order that itself takes (M*N)log(M*N) time. So the total time complexity to search any element here is O((M * N) log(M * N)) + O(N + M) which very poor when it is compared with the time complexity of Linear Search which is just O(N*M). Therefore, Linear Search is used for searching in an unsorted array, not Binary Search.

Below is the implementation for Binary search in 2D arrays:

// TC: O(N + M)
// SC: O(1)
func searchMatrix2(_ matrix: [[Int]], _ target: Int) -> Bool {
    var row = 0;
    var col = matrix[row].count - 1;
    while row < matrix.count && col >= 0 {
        if matrix[row][col] == target {
            return true// row, col
        }
        if matrix[row][col] < target {
            row+=1 // Target lies in further row
        } else {
            col-=1  // Target lies in previous column
        }
    }
    return false
}
let searchMatrix = [[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]]
let targetToSearch = 5
let opSearchElement = searchMatrix2(searchMatrix, targetToSearch)
print(" opSearchElement --- ", opSearchElement)// true

Improved Binary Search in a 2D Array: 

We can reduce the time by converting 2D array to 1D array. Add row one after another and search the item then convert it to 2D again.

1	2	3
4	5	6
7	8	9

Convert it to 1D array 

1

2

3

4

5

6

7

8

9

Now apply normal binary search and get the result. Not necessary store the 1D in new array you can create it virtually by converting row, col value to 1D index vice-versa 1D to row, col value.   

// Approch 2: by converring it into 1D matrix.
// TC: O(log N*M)
// SC: O(1)
func searchMatrix2Using1D(_ matrix: [[Int]], _ target: Int) -> Bool {
    var row = matrix.count
    var col = matrix[0].count
    var l = 0, h = row * col - 1
    while (l <= h) {
        let mid = l + ((h - l) / 2)
        let tC = mid % col
        let tR = (mid / col)
        let val = matrix[tR][tC]
        if (val == target){
            return true
        }
        if (val < target) {
            l = mid + 1
        } else {
            h = mid - 1
        }
    }
    return false
}