0

I have a matrix (n*n) which all its columns are ordered in non descending order while the rows are not ordered - I know that each value in a row is smaller than all the values in the rows below, but the values inside the rows are not sorted, although they are all either smaller or identical to the values in the row below.

I need to find a value in this matrix in O(n). I thought of running a binary search on one of the columns until I get into one cell which is the closest one to my searched value (in case, of course, I did not find the value during the search).

Then, I will check for the searched value in the row of the cell and in the row above (if cell > searched_val) or the row below (if cell < searched_val).

Will it work? Will it also work in case that the column is full with identical values?

Ido
  • 573
  • 4
  • 11
  • This question looks like an exact duplicate of [Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?](http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom) – Tim Biegeleisen Jun 05 '15 at 07:18
  • Take this matrix (4*4): {{10,1,3,2},{10,11,12,13},{10,21,23,22},{10,100,45,28}} - this is a non descending order of the columns while the rows are not ordered. Saddle back search will not help here. – Ido Jun 05 '15 at 08:24

1 Answers1

0

I know that each value in a row is smaller than all the values in the rows below

This means that the rows are ordered in ascending order

So, starting from your definition, both rows and columns are ordered.

In this way you can search your Matrix as an array of size n*n. Binary search in this case will go:

O(log(n*n)) = O(2*log(n)) = O(log(n)) < O(n)

You just have to define an index that moves in the Matrix in ascending (or descending) order.

B3rn475
  • 1,057
  • 5
  • 14
  • Let's say I have this matrix (4*4): {{10,1,3,2},{10,11,12,13},{10,21,23,22},{10,100,45,28}} - this is a non descending order of the columns while the rows are not ordered. Let's say I am looking for the value 21. I can run binary search on all the columns but it will give me O(n*logn). – Ido Jun 05 '15 at 08:22
  • so what about "all its columns are ordered in non descending order"? – B3rn475 Jun 05 '15 at 11:02
  • The columns are non descending - but the rows can be unordered as long as all the values in one row are smaller or equal to the values in the row below. – Ido Jun 06 '15 at 16:53
  • The problem here is that the worst case is O(n^2), It is the Whole Matrix filled with a value that is not the one you are looking for. – B3rn475 Jun 11 '15 at 07:54