## Matrix Search

### August 17, 2018

Our strategy is to perform binary search on each row, stopping when we find the target value or reporting failure after searching all rows:

(define (matsearch lt? x mat) (let ((len (vector-length mat))) (let loop ((r 0)) (cond ((= r (vector-length mat)) #f) ((bsearch lt? x (vector-row r mat)) => (lambda (c) (list r c))) (else (loop (+ r 1))))))

This has time complexity O(*n* log *n*), as there are *n* rows, each of which takes logarithmic time for the binary search. Here are some examples:

> (matsearch < 8 '#(#(2 5 8) #(1 4 7) #(3 6 9))) (0 2) > (matsearch < 6 '#(#(2 5 8) #(1 4 7) #(3 6 9))) (2 1) > (matsearch < 0 '#(#(2 5 8) #(1 4 7) #(3 6 9))) #f

The binary search comes from a previous exercise. You can run the program at https://ideone.com/f2TtnH.

Advertisements

Here’s a solution in C.

Output:

Klong version 2

[sourcecode lang="css"]

.comment(“end-of-comment”)

[n s] – Set up 2 local variables

s::#x – Get size of matrix (Number of row/columns)

(,/:~x) – Flatten matrix into 1 row

?y – Find second parameter in flattened matrix

n::… – Assign location of 2nd parameter to n

If not found, assign []

:[0=#n; – If 2nd parameter not found (Size of parameter ([]) is 0)

[-1 -1] – True –> return [-1 -1]

False

n::n@0 – Get element in flattened matrix and assign to n

(…)!s – Get column by getting remainer of n and s

(_n%s) – Get row by integer dividing element by s

(!n…),(n::…) – Return list of row and column

ms::{…} – Make function and name it ms

.p(…) – Print argument

‘!10 – Run function against each element of list from 0 to 9

end-of-comment

Examples:

{{.p(x,” –> “,,ms([[2 5 8][1 4 7][3 6 9]]; x))}’!10}();””

[0 –> [-1 -1]]

[1 –> [1 0]]

[2 –> [0 0]]

[3 –> [2 0]]

[4 –> [1 1]]

[5 –> [0 1]]

[6 –> [2 1]]

[7 –> [1 2]]

[8 –> [0 2]]

[9 –> [2 2]]

“”

Klong version 3

@programmingpraxis: Please delete Klong version 2. Thanks.

Mumps version