Task — Search matrix

You are given a 5x5 matrix filled with integers such that each row is sorted from left to right and the first integer of each row is greater than the last integer of the previous row.

Write a script to find a given integer $seek in the matrix using an efficient search algorithm.

Examples

Example 1
Matrix: [  1,  2,  3,  5,  7 ]
        [  9, 11, 15, 19, 20 ]
        [ 23, 24, 25, 29, 31 ]
        [ 32, 33, 39, 40, 42 ]
        [ 45, 47, 48, 49, 50 ]

Input: 35
Output: 0 since it is missing in the matrix

Input: 39
Output: 1 as it exists in the matrix

Analysis

Well, I wonder what 'using an efficient search algorithm' means?

First let's reduce the matrix to an array @cells.

If the matrix were large - say more than 30x30 - then I'd do a binary chop, something like:

• Set $left == 0; $right == 29
• loop
  • set $bound = int(($left + $right) / 2)
  • if $right - $left <= 1 output 0 and quit
  • If $seek == $bound output 1 and quit
  • if $seek < $matrix($bound)
    set $right = $bound else set $left = $bound

The loop will execute a maximum of log2($rows * $cells) times, so 30 x 30, about 10 times (as 2 ** 10 = 1024).

But for a smaller matrix I'd do this:

• Push $seek onto the end of @cells
• Set $place = -1
• Then do
  { $place ++ } until ($cells[$place] == $seek)
• If $place < @cells - 1 output 1 else output 0

This is very fast because the loop contains just two primitive operations:

• add 1 to $place
• repeat unless $cells[$place] == $seek

In a compiled language that's typically just 2 machine instructions and I imagine that in Perl it may be the same or close to it.

So unless the matrix is pretty large, or possibly if you need to do this operation on millions of matrices, I'd go for the second solution - and indeed I've delivered that solution in code for many clients. And here it is.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-03
use utf8;     # Week 111 - task 1 - Search matrix
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

search_matrix([  1,  2,  3,  5,  7 ,
                 9, 11, 15, 19, 20 ,
                23, 24, 25, 29, 31 ,
                32, 33, 39, 40, 42 ,
                45, 47, 48, 49, 50], $_) for (0, 1, 11, 26, 50, 51);
say '-' x 50;         
search_matrix([  0,  2,  3,  5,  6,  7 ,
                 9, 11, 15, 19, 20, 22 ,
                23, 24, 25, 29, 30, 31 ,
                32, 33, 39, 40, 42, 43 ,
                45, 47, 48, 49, 50, 59 ,
                60, 70, 80, 85, 90, 99], $_) for (0, 1, 11, 40, 99, 100);

sub search_matrix {
    
    my (@cells, $seek, $size, $place);
    
    # initialise
    @cells = @{$_[0]};
    $seek = $_[1];
    $size = int(sqrt(@cells));
    say qq[\nInput:  \$seek = $seek];
    print_matrix(\@cells, $size, 'Matrix:');

    # fast search of matrix
    push(@cells, $seek);
    $place = -1;
    do { $place ++ } until ($cells[$place] == $seek);
    
    # show result
    if ($place < @cells - 1) {
        say qq[Output: 1 (cell ] . $place % $size . ', ' . int($place / $size) . ')';
    } else {
        say qq[Output: 0];
    }
}

sub print_matrix {
    
    my ($matrix, $cols, $legend, $row, $col, $rows, $w);

    # print array as a matrix with $cols columns
    ($matrix, $cols, $legend) = @_;
    $rows = @$matrix / $cols - 1;
    $w = 0;
    
    # get max width
    for (0 .. @$matrix - 1) {
        $w = length($$matrix[$_]) if length($$matrix[$_] > $w);
    }

    # loop over rows and cols
    for $row (0 .. $rows) {
        print qq{$legend [ };
        for $col (0 .. $cols - 1) {
            printf("%${w}s", $$matrix[$row * $cols + $col]); 
            print $col == $cols - 1 ? ' ' : ', ';
        }
        say $row == $rows ? ']' : '],';     
        $legend = ' ' x length($legend) if $row == 0;
    }
}

28 lines of code

I completed this challenge after the closing date
and it has not been submitted to GitHub

Output

Input:  $seek = 0
Matrix: [  1,  2,  3,  5,  7 ],
        [  9, 11, 15, 19, 20 ],
        [ 23, 24, 25, 29, 31 ],
        [ 32, 33, 39, 40, 42 ],
        [ 45, 47, 48, 49, 50 ]
Output: 0

Input:  $seek = 1
Matrix: [  1,  2,  3,  5,  7 ],
        [  9, 11, 15, 19, 20 ],
        [ 23, 24, 25, 29, 31 ],
        [ 32, 33, 39, 40, 42 ],
        [ 45, 47, 48, 49, 50 ]
Output: 1 (cell 0, 0)

Input:  $seek = 11
Matrix: [  1,  2,  3,  5,  7 ],
        [  9, 11, 15, 19, 20 ],
        [ 23, 24, 25, 29, 31 ],
        [ 32, 33, 39, 40, 42 ],
        [ 45, 47, 48, 49, 50 ]
Output: 1 (cell 1, 1)

Input:  $seek = 26
Matrix: [  1,  2,  3,  5,  7 ],
        [  9, 11, 15, 19, 20 ],
        [ 23, 24, 25, 29, 31 ],
        [ 32, 33, 39, 40, 42 ],
        [ 45, 47, 48, 49, 50 ]
Output: 0

Input:  $seek = 50
Matrix: [  1,  2,  3,  5,  7 ],
        [  9, 11, 15, 19, 20 ],
        [ 23, 24, 25, 29, 31 ],
        [ 32, 33, 39, 40, 42 ],
        [ 45, 47, 48, 49, 50 ]
Output: 1 (cell 4, 4)

Input:  $seek = 51
Matrix: [  1,  2,  3,  5,  7 ],
        [  9, 11, 15, 19, 20 ],
        [ 23, 24, 25, 29, 31 ],
        [ 32, 33, 39, 40, 42 ],
        [ 45, 47, 48, 49, 50 ]
Output: 0
--------------------------------------------------

Input:  $seek = 0
Matrix: [  0,  2,  3,  5,  6,  7 ],
        [  9, 11, 15, 19, 20, 22 ],
        [ 23, 24, 25, 29, 30, 31 ],
        [ 32, 33, 39, 40, 42, 43 ],
        [ 45, 47, 48, 49, 50, 59 ],
        [ 60, 70, 80, 85, 90, 99 ]
Output: 1 (cell 0, 0)

Input:  $seek = 1
Matrix: [  0,  2,  3,  5,  6,  7 ],
        [  9, 11, 15, 19, 20, 22 ],
        [ 23, 24, 25, 29, 30, 31 ],
        [ 32, 33, 39, 40, 42, 43 ],
        [ 45, 47, 48, 49, 50, 59 ],
        [ 60, 70, 80, 85, 90, 99 ]
Output: 0

Input:  $seek = 11
Matrix: [  0,  2,  3,  5,  6,  7 ],
        [  9, 11, 15, 19, 20, 22 ],
        [ 23, 24, 25, 29, 30, 31 ],
        [ 32, 33, 39, 40, 42, 43 ],
        [ 45, 47, 48, 49, 50, 59 ],
        [ 60, 70, 80, 85, 90, 99 ]
Output: 1 (cell 1, 1)

Input:  $seek = 40
Matrix: [  0,  2,  3,  5,  6,  7 ],
        [  9, 11, 15, 19, 20, 22 ],
        [ 23, 24, 25, 29, 30, 31 ],
        [ 32, 33, 39, 40, 42, 43 ],
        [ 45, 47, 48, 49, 50, 59 ],
        [ 60, 70, 80, 85, 90, 99 ]
Output: 1 (cell 3, 3)

Input:  $seek = 99
Matrix: [  0,  2,  3,  5,  6,  7 ],
        [  9, 11, 15, 19, 20, 22 ],
        [ 23, 24, 25, 29, 30, 31 ],
        [ 32, 33, 39, 40, 42, 43 ],
        [ 45, 47, 48, 49, 50, 59 ],
        [ 60, 70, 80, 85, 90, 99 ]
Output: 1 (cell 5, 5)

Input:  $seek = 100
Matrix: [  0,  2,  3,  5,  6,  7 ],
        [  9, 11, 15, 19, 20, 22 ],
        [ 23, 24, 25, 29, 30, 31 ],
        [ 32, 33, 39, 40, 42, 43 ],
        [ 45, 47, 48, 49, 50, 59 ],
        [ 60, 70, 80, 85, 90, 99 ]
Output: 0