## Search In An Ascending Matrix

### February 10, 2012

We use the matrix library from the Standard Prelude and define the sample matrix as

`(define m (vector #(1 5 7 9) #(4 6 10 15) #(8 11 12 19) #(14 16 18 21)))`

Our search strategy starts in the top-right corner of the matrix. If the current element in the matrix is equal to the key *k*, we are finished. If the key *k* is less than the current element then it cannot be present in the current column, so move to the element to the left of the current element and repeat the search. If the key *k* is greater than the current element then it cannot be present in the current row, so move to the element below the current element and repeat the search. If any move takes you outside the bounds of the matrix, report failure and stop:

`(define (search m k)`

(let ((max-r (- (matrix-rows m) 1)) (max-c (- (matrix-cols m) 1)))

(let loop ((r 0) (c max-c))

(cond ((or (negative? c) (< max-r r)) #f)

((< k (matrix-ref m r c)) (loop r (- c 1)))

((< (matrix-ref m r c) k) (loop (+ r 1) c))

(else (values r c))))))

This algorithm takes time *O*(*m* + *n*) because at each step you advance the current pointer one element in either direction, a maximum of *m*−1 steps left and *n*−2 steps down. Here are two examples:

`> (search m 11)`

2

1

> (search m 13)

#f

You can run the program at http://programmingpraxis.codepad.org/tOTusNoj.

Not optimal, but has the required complexity.

“If the key k is greater than the current element then it cannot be present in the current row”

I’m sorry, I don’t understand that. Let’s look for the key 5 in the example. We start with element 1 and the condition quoted applies. So we go down. But wait, 5 can be actually found in the row in question.

Hmm…

Arthur, you apparently missed that programmingpraxis’s algorithm starts at the top-right corner which is 9 in this example.

Yup, that’s it. Thanks. I was starting at the top-left.

a while loop might be better here.

matrixsearch

Clever algorithm, OP. Haven’t seen this one before.

Correct me if I’m wrong, but all solutions posted by others (including OP) only move up or down, but not both, per iteration. The algorithms will not move both left and right in any one iteration.

The solution I posted can move both left and right if the conditions allow it.

Is there a reason you only move one direction per iteration?

Whoops, got my directions all mixed up.

All other algorithms move either left or down, but not both, per iteration. The algorithms will not move both left and down in any one iteration.

The solution I posted can move left and down simultaneously if the conditions allow it.

Is there a reason you only move one direction per iteration?

def find(m, k):

h=0

for i in m:

v=0

if k<=i[-1]:

for j in i:

if j==k: return h,v

v+=1

h+=1

return "Not found"

#Usage Example

M = [ [ 1, 5, 7, 9 ],

[ 4, 6, 10, 15 ],

[ 8, 11, 12, 19 ],

[ 14, 16, 18, 21 ] ]

print find(M, 18)

I am pretty new to this site, and don’t know if this is how we post answers, but please comment if its not like this.

The same idea as ProgrammingPraxis’ solution, except I happend to start at the lower left corner instead of the upper right.

Sorry, there’s a type in line 17. Here’s the corrected code:

Not optimal, but wanted to post what I got:

object AscendMatrixSearch extends App {

val mat = List(List(1, 5, 7, 9), List(4, 6, 10, 15), List(8, 11, 12, 19), List(14, 16, 18, 21))

def find(v: Int, mat: List[List[Int]]) =

for (row <- mat if v <= row.last; i <- row if i == v) println("Found " + v)

find(11, mat)

find(13, mat)

}

Again, not optimal as what’s here, but forgot indices

object AscendMatrixSearch extends App {

val mat = List(List(1, 5, 7, 9), List(4, 6, 10, 15), List(8, 11, 12, 19), List(14, 16, 18, 21))

def find(v: Int, mat: List[List[Int]]) =

for (i <- 0 until mat.length; row = mat(i); j <- 0 until row.length if row(j) == v) println("Found " + v + " at (" + i + ", " + j + ")")

find(15, mat)

find(11, mat)

find(33, mat)

find(-24, mat)

}

Forgot filter on row, sorry for three posts (this is Scala code is that allowed here?)

object AscendMatrixSearch extends App {

val mat = List(List(1, 5, 7, 9), List(4, 6, 10, 15), List(8, 11, 12, 19), List(14, 16, 18, 21))

def find(v: Int, mat: List[List[Int]]) =

for (i <- 0 until mat.length if v <= mat(i).last; row = mat(i); j <- 0 until row.length if row(j) == v)

println("Found " + v + " at (" + i + ", " + j + ")")

find(15, mat)

find(11, mat)

find(33, mat)

find(-24, mat)

}

My attempt at a haskell solution. Probably could be done much more succinctly, but well

My recoursive solution:

My Attempt in Python. Basic flow is:

Scan a column top to down and stop when you hit a higher value.

Then move a column right and try finding a hit there.

Keep repeating the above 2 steps. You will eventually snake your way through the matrix.

Room to optimize this further.

In Racket:

(define matrix ‘#(#(1 5 7 9)

#(4 6 10 15)

#(8 11 12 19)

#(14 16 18 21)))

(define matrix-rows vector-length)

(define (matrix-cols m)

(vector-length (vector-ref m 0)))

(define (matrix-ref m r c)

(vector-ref (vector-ref m r) c))

(define (find-in-ascending-matrix num)

(let loop ((r0 0)

(r1 (sub1 (matrix-rows matrix)))

(c0 0)

(c1 (sub1 (matrix-cols matrix))))

(if (and r0 r1 c0 c1 (>= r1 r0) (>= c1 c0))

(if [= num (matrix-ref matrix r0 c0)]

(vector r0 c0)

(loop

(for/first ([i (in-range r0 (add1 r1))]

#:when (>= (matrix-ref matrix i c1) num))

i)

(for/first ([i (in-range r1 (sub1 r0) -1)]

#:when (= (matrix-ref matrix r1 i) num))

i)

(for/first ([i (in-range c1 (sub1 c0) -1)]

#:when (<= (matrix-ref matrix r0 i) num))

i)

))

#f)))

Just noticed the method to post source: