How To Search An Element In Sorted Matrix In Linear Time

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.