Categories
tech

How To Search An Element In Sorted Matrix In Linear Time

Author profile picture

We need to seek for a worth x in a taken care of matrix M. If exists, then go back its coordinates (i, j), else go back (-1, -1).

Let us believe the above matrix for instance. In this situation, we’re going to seek for the price 12. Since 12 is provide within the matrix, the set of rules will have to go back its coordinates (2, 1)

A easy method is to traverse the entire values within the matrix and test if it is the same as 12.

Time Complexity
The worst case time complexity of the above set of rules will probably be
O(n x m) = O(n²) when n = m

The above set of rules behaves worse for enormous values of n and m. Let us glance into the environment friendly set of rules now.

Algorithm

  1. Start from Top Right place (0, m – 1) within the matrix M
  2. If the price is the same as x go back (0, m – 1)
  3. Move one row down if the present worth is not up to x
  4. Move one column left if the present worth is larger that x

Let us observe this set of rules into our matrix M. We are going to seek for the price 12 in M

1. Start from the Top Right worth at M[0][4]. 5 is not up to 12, so 12 will have to be someplace within the backside of the matrix since all row and column values are taken care of in ascending order. So we transfer one row down.

2. The worth 10 at M[1][4] may be not up to 12, so we transfer one row down

3. The worth 15 at M[2][4] is larger than 12, so 12 will have to be someplace within the left of the matrix, so we transfer one column left.

4. The worth 14 at M[2][3] may be more than 12, so we transfer one column left

5. The worth 13 at M[2][2] is larger than 12, so we transfer one column left

6. The worth at M[2][1] is the same as 12, so we go back its index (2, 1)

Time Complexity

The worst case time complexity of the above set of rules will probably be
O(n + m) = O(2n) = O(n) when n = m, as a result of we will be able to be iterating all rows and all columns as soon as if is on the backside left place (n – 1, 0)

You can to find the Java answer for this set of rules within the Github repo.

Thank you 🙏 👋🤘

Tags

The Noonification banner

Subscribe to get your day by day round-up of most sensible tech tales!