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

Pages: 1 2

6 Responses to “Matrix Search”

  1. Daniel said

    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:

    $ ./a.out
    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)
    10: (-1,-1)
    
  2. 
    (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.
    
    
  3. 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

        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]]
    “”

  4. 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]]
    ""
    
  5. @programmingpraxis: Please delete Klong version 2. Thanks.

  6. 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
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: