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.
Programming Praxis 
Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> ssize_t search(int* matrix, int x, size_t m, size_t n) { for (size_t i = 0; i < m; ++i) { size_t lo = i * n; size_t hi = lo + n; while (hi > lo) { size_t mid = lo + (hi - lo) / 2; int val = matrix[mid]; if (val < x) { lo = mid + 1; } else if (val > x) { hi = mid; } else { return mid; } } } return -1; } int main(void) { int matrix[] = { 2, 5, 8, 1, 4, 7, 3, 6, 9 }; size_t m = 3; size_t n = 3; for (int x = 0; x <= 10; ++x) { ssize_t idx = search(matrix, x, m, n); ssize_t i = -1; ssize_t j = -1; if (idx >= 0) { j = idx % n; i = (idx - j) / n; } printf("%d: (%zd,%zd)\n", x, i, j); } return EXIT_SUCCESS; }Output:
(defun matrix-search-1 (m x &key (test (function =))) (find x (make-array (reduce (function *) (array-dimensions m)) :displaced-to m) :test test)) ;; Now, notice that: (log 1000000 2) = 19.931568 ;; So if your matrices are smaller than 1 million elements, (eg. 1000 x 1000 or 100 x 10000), ;; you can stop here. ;; If we can't amortize pre-processing, then we'll have to search each rown independently. ;; The time complexity will be: O(rows*logâ‚‚(cols)) ;; This is probably the expected answer by an interrogator ;; ( cf. https://www.youtube.com/watch?v=NA9B6-s6r7Y ) ;; but notice how slower it is on small matrices! ;; (There's no right answer, there's the answer expected by the interrogator, ;; and the other answers). (defun matrix-search-2 (m x &key (lessp (function <))) (loop :for row :below (array-dimension m 0) :do (multiple-value-bind (found col) (dichotomy (lambda (col) (cond ((funcall lessp x (aref m row col)) -1) ((funcall lessp (aref m row col) x) +1) (t 0))) 0 (array-dimension m 1)) (when found (return-from matrix-search-2 (values (list row col) (aref m row col)))))) nil) ;; If we can pre-process the matrix, then the simpliest and most ;; efficient thing to do is to pre-compute all the results, which will ;; allows us to perform a dichotomic search (defvar *matrix-search-3-cache* (cons nil nil)) (defun matrix-search-3 (m x &key (lessp (function <))) (let ((results (if (eql (car *matrix-search-3-cache*) m) (cdr *matrix-search-3-cache*) (setf (car *matrix-search-3-cache*) m (cdr *matrix-search-3-cache*) (let ((results (make-array (reduce (function *) (array-dimensions m)))) (i -1)) (loop :for r :below (array-dimension m 0) :do (loop :for c :below (array-dimension m 1) :do (setf (aref results (incf i)) (cons (aref m r c) (list r c))))) (sort results (function <) :key (function car))))))) (multiple-value-bind (found index) (dichotomy-search results x (lambda (a b) (cond ((funcall lessp a b) -1) ((funcall lessp b a) +1) (t 0))) :key (function car)) (when found (values (cdr (aref results index)) (car (aref results index))))))) (defun gen (rows cols) (let ((p (* rows cols))) (make-array (list rows cols) :initial-contents (map 'list (lambda (row) (sort (map 'list (function cdr) row) (function <))) (group-by (sort (map 'vector (lambda (i) (cons (random p) i)) (iota p)) (function <) :key (function car)) cols))))) (defun benchmark () (loop :for m :in (list (gen 100 100) #2A((0 4 10 12 15 17) (1 11 16 19 21 22) (2 5 6 7 8 9) (3 13 14 18 20 23)) #2A((2 5 8) (1 4 7) (3 6 9))) :collect (cons (array-dimensions m) (loop :for search :in '(matrix-search-1 matrix-search-2 matrix-search-3) :collect (cons search (chrono-run-time (loop :for x :below 10000 :do (funcall search m x)))))))) (benchmark) ;; --> (((100 100) (matrix-search-1 . 1.7939949999999953D0) (matrix-search-2 . 0.8034000000006927D0) (matrix-search-3 . 0.023526000000856584D0)) ;; ((4 6) (matrix-search-1 . 0.013214000002335524D0) (matrix-search-2 . 0.04642099999909988D0) (matrix-search-3 . 0.01174199999877601D0)) ;; ((3 3) (matrix-search-1 . 0.007996000000275671D0) (matrix-search-2 . 0.03040799999871524D0) (matrix-search-3 . 0.010618000000249594D0))) ;; So you can see that matrix-search-2 is the slowest in all cases! ;; and that matrix-search-1, the silliest O(rows*cols) implementation ;; is also the fastest for practical cases (small matrices), and if ;; you have big matrices and lots of searches, you better keep the ;; simple algorithm by performing a O(rows*cols*log(rows*cols)) ;; precomputing to be able to find the results in O(log(rows*cols)). ;; And of course, if your matrices contain really the integers in ;; (iota (* rows cols)), then you can lookup the results in 1 access ;; just indexing the result vector which contains the coordinates of ;; the integer.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
.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 ms::{[n s]; s::#x; n::(,/:~x)?y; :[0=#n; [-1 -1]; (_n%s),(n::n@0)!s]} 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]] ""@programmingpraxis: Please delete Klong version 2. Thanks.
Mumps version
matrixsearch ; q ; go(matrix,num) ; Find row,column of n in matrix n found,i,j,rtn s found=0,rtn="-1,-1" f i=1:1:3 d q:found . f j=1:1:3 d q:found . . i $p(matrix(i),",",j)=num d . . . s rtn=(i-1)_","_(j-1),found=1 q rtn Examples: GTM>zwrite arr(1)="2,5,8" arr(2)="1,4,7" arr(3)="3,6,9" GTM>f i=0:1:9 w !,i," --> ",$$go^matrixsearch(.arr,i) 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