# How to search an element in Sorted Integer matrix ?

Question : Given an m*n 2D sorted matrix of integers, write a program to find if the given integer exists in the matrix.
The matrix has the properties below:

1. Integers in each row are sorted from left to right.
2. The first integer of each row is greater than the last integer of the previous row(Increasing order matrix)
3. Column values count is equal for matrix(Symmetric matrix)

Approach #1 By removing row and col in each comparisons . Starting from the top right of matrix, move towards the bottom left in search of the target element

``````// TC O(m+n)
// SC O(1)
func searchMatrix(matrix: [[Int]],  target: Int) ->Bool {
if matrix.isEmpty {
return false
}
var matrixCount = matrix.count
var matrixRowElementsCount = matrix[0].count
var row = 0
var col = matrixCount - 1
while row < matrixRowElementsCount && col >= 0 {
if(matrix[row][col] == target) {
return true
} else if(matrix[row][col] < target) {
row = row + 1
} else {
col = col - 1
}
}
return false
}

let matrix: [[Int]] =
[[23, 25, 35, 37],
[40, 41, 42, 43],
[50, 60, 74, 80]]

let k = 80
print("is element present in matrix", searchMatrix(matrix: matrix, target: k))// true``````

Approach #2 Binary Search : Considering the matrix as a single array, perform a binary search for the target.

``````//TC O(log(m*n)) = O(log(m) + log(n))
//SC: O(1)
func searchMatrix2(matrix: [[Int]],  target: Int) ->Bool {
if matrix.isEmpty {
return false
}
var matrixCount = matrix.count
var matrixRowElementsCount = matrix[0].count
var left = 0
var right = matrixRowElementsCount * matrixCount - 1

while left != right {
let mid = (left + right - 1) / 2
if (matrix[mid / matrixRowElementsCount][mid % matrixRowElementsCount] < target) {
left = mid + 1
} else {
right = mid
}
}
if (matrix[right / matrixRowElementsCount][right % matrixRowElementsCount] == target) {
return true
} else {
return false
}
}
let matrix: [[Int]] =
[[23, 25, 35, 37],
[40, 41, 42, 43],
[50, 60, 74, 80]]

let k = 80
print("is element present in matrix", searchMatrix2(matrix: matrix, target: k))// true``````
###### #Approach 2: More use of binary
``````//TC: O(log(m*n))
// SC: O(1)
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
if matrix.isEmpty  { return false}
var lo = 0
let n = matrix.count
let m = matrix[0].count
var hi = (n * m) - 1

while lo <= hi {
var  mid = (lo + (hi - lo) / 2)
if matrix[mid/m][mid % m] == target {
return true
}
if matrix[mid/m][mid % m] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return false
}

let matrixSorted = [[1,3,5,7],
[10,11,16,20],
[23,30,34,60]]
let elementToSearch = 3
let isFoundInMatrix = searchMatrix(matrixSorted, elementToSearch)
print("is FoundInMatrix ", isFoundInMatrix)// true``````