1,437 reads
How To Search An Element In Sorted Matrix In Linear Time
by Ganesh Kumar MAugust 11th, 2020
Too Long; Didn't Read
If x exists, then return its coordinates (i, j), else return (-1, -1). In this example, we are going to search for the value 12 in a sorted matrix M. The worst case time complexity of the above algorithm will be O(O(n x m) = O(n²) when n = m, because we will be iterating all rows and all columns once if x is at the bottom left position (n - 1, 0) If the value is equal to x return (0, m - 1) Move one row down if the current value is less than x, then move one column left.
Statement
We have to search for a value x in a sorted matrix M. If x exists, then return its coordinates (i, j), else return (-1, -1).
Let us consider the above matrix as an example. In this example, we are going to search for the value 12. Since 12 is present in the matrix, the algorithm should return its coordinates (2, 1)
Simple Approach
A simple approach is to traverse all the values in the matrix and check if it is equal to 12.
Time Complexity
The worst case time complexity of the above algorithm will be
O(n x m) = O(n²) when n = m
Efficient Approach
The above algorithm behaves worse for large values of n and m. Let us look into the efficient algorithm now.
Algorithm
- Start from Top Right position (0, m - 1) in the matrix M
- If the value is equal to x return (0, m - 1)
- Move one row down if the current value is less than x
- Move one column left if the current value is greater that x
Let us apply this algorithm into our matrix M. We are going to search for the value 12 in M
1. Start from the Top Right value 5 at M[0][4]. 5 is less than 12, so 12 should be somewhere in the bottom of the matrix since all row and column values are sorted in ascending order. So we move one row down.
2. The value 10 at M[1][4] is also less than 12, so we move one row down
3. The value 15 at M[2][4] is greater than 12, so 12 should be somewhere in the left of the matrix, so we move one column left.
4. The value 14 at M[2][3] is also greater than 12, so we move one column left
5. The value 13 at M[2][2] is greater than 12, so we move one column left
6. The value at M[2][1] is equal to 12, so we return its index (2, 1)
Time Complexity
The worst case time complexity of the above algorithm will be
O(n + m) = O(2n) = O(n) when n = m, because we will be iterating all rows and all columns once if x is at the bottom left position (n - 1, 0)
You can find the Java solution for this algorithm in the Github repo.
https://github.com/ganeshkumarm1/DSAlgo/tree/master/src/com/dsalgo/Algorithms/BinarySearch2D
Thank you 🙏 👋🤘
L O A D I N G
. . . comments & more!
. . . comments & more!
