Find Target In A Matrix

August 1, 2017

The solution starts from the top-right corner and works down and left, one cell at a time. If the current cell is larger than the target, move left. If the current cell is smaller than the target, move down. If the current cell is equal to the target, report success. If you reach the left or bottom edge of the matrix without finding the target, report failure:

(define (target m x)
  (let loop ((r 0) (c (- (matrix-cols m) 1)))
    (cond ((or (negative? c) (= (matrix-rows m) r)) #f)
          ((< x (matrix-ref m r c)) (loop r (- c 1)))
          ((< (matrix-ref m r c) x) (loop (+ r 1) c))
          (else (values r c)))))

We return the row and column coordinates of the target, or #f if it is not found. Here’s an example:

> (define m '#(
    #( 1 12 43 87)
    #( 9 25 47 88)
    #(17 38 48 92)
    #(45 49 74 95)))
> (target m 72)
#f
> (target m 38)
2
1

The algorithm is clearly O(m + n) for an m by n matrix. You can run the program at http://ideone.com/YR0tv0.

Advertisements

Pages: 1 2

10 Responses to “Find Target In A Matrix”

  1. Rutger said

    In Python3. Starting inspecting upper right index for the target value. Due to the fact that the Matrix is already ordered, this means that a larger target value should be beneath current index. If it is smaller, move index one to the left and repeat.

    
    matrix = [[1,12,43,87], [9,25,47,88], [17,38,48,92], [45,49,74,95]]
    
    
    def find_target(m, value):
    	i,j = 0,len(m)-1
    	while m[i][j] != value:
    		if i >= len(m) or j < 0:
    			return False
    		if m[i][j] < value:
    			i += 1
    		else:
    			j -= 1
    
    	return True
    
    print(find_target(matrix, 87))
    print(find_target(matrix, 1))
    print(find_target(matrix, 25))
    print(find_target(matrix, 95))
    print(find_target(matrix, -1))
    print(find_target(matrix, 45))
    print(find_target(matrix, 2))
    
    #True
    #True
    #True
    #True
    #False
    #True
    #False
    
  2. Jan Van lent said

    Recursive algorithm in Python 3.6.
    The function ‘find’ returns a generator of indices. This should be efficient for testing whether the target is present or for finding the location of all occurrences.

    def find(A, t):
        def rec(i, j, m, n):
            if m == 0 or n == 0 or t < A[i][j] or A[i+m-1][j+n-1] < t:
                return
            else:
                if m == 1 and n == 1:
                    if A[i][j] == t:
                        yield (i, j)
                    else:
                        return
                else:
                    yield from rec(i, j, m//2, n//2)
                    yield from rec(i+m//2, j, m-m//2, n//2)
                    yield from rec(i, j+n//2, m//2, n-n//2)
                    yield from rec(i+m//2, j+n//2, m-m//2, n-n//2)
        return rec(0, 0, len(A), len(A[0]))
    
    def printmat(A):
        print("[", ",\n  ".join(map(str, A)), "]")
    
    example = """
     1 12 43 87
     9 25 47 88
    17 38 48 92
    45 49 74 95
    """
    A = [ list(map(int, line.strip().split()))
          for line in example.strip().split("\n") ]
    printmat(A)
    
    for row in A:
        for el in row:
            #print(el)
            result = list(find(A, el))
            #print(result)
            print([(el, A[i][j]) for (i, j) in result])
    
    for el in [0, 26, 50]:
        print(el, list(find(A, el)))
    
    m, n = 7, 9
    B = [ [ i**2 + j**2 for j in range(n) ] for i in range(m) ]
    printmat(B)
    print(list(find(B, 25)))
    
  3. Jan Van lent said

    Slightly more compact:

    def find(A, t):
        def rec(i, j, m, n):
            if m > 0 and n > 0 and A[i][j] <= t <= A[i+m-1][j+n-1]:
                if m == 1 and n == 1 and A[i][j] == t:
                    yield (i, j)
                else:
                    yield from rec(i, j, m//2, n//2)
                    yield from rec(i+m//2, j, m-m//2, n//2)
                    yield from rec(i, j+n//2, m//2, n-n//2)
                    yield from rec(i+m//2, j+n//2, m-m//2, n-n//2)
        return rec(0, 0, len(A), len(A[0]))
    
  4. Daniel said

    Here’s an O(log(n) + log(m)) solution in Python.

    It first uses binary search on the first row to find a candidate column. It then uses binary search on that column.

    If that fails, it uses binary search on the first column to find a candidate row. It then uses binary search on that row.

    Numpy’s searchsorted function was used for binary search.

    import numpy as np
    
    def array_find(array, element):
        idx = np.searchsorted(array, element, side='right') - 1
        return element == array[idx]
    
    def matrix_find(matrix, element):
        col_idx = np.searchsorted(matrix[0, :], element, side='right') - 1
        if array_find(matrix[:, col_idx], element):
            return True
        row_idx = np.searchsorted(matrix[:, 0], element, side='right') - 1
        if array_find(matrix[row_idx, :], element):
            return True
        return False
    
    M = np.array([
        [ 1, 12, 43, 87],
        [ 9, 25, 47, 88],
        [17, 38, 48, 92],
        [45, 49, 74, 95]
    ])
    
    for x in range(-100,100):
        if matrix_find(M, x):
            print x
    
  5. Daniel said

    Here’s the output of the program I just posted.

    1
    9
    12
    17
    25
    38
    43
    45
    47
    48
    49
    74
    87
    88
    92
    95
    
  6. Daniel said

    My previous solution does not work.

    The following example doesn’t find the 48.

    M = np.array([
        [1,  12, 43, 87],
        [9,  25, 47, 88],
        [17, 48, 50, 92],
        [45, 49, 74, 95]
    ])
    
    for x in range(-100, 100):
        if matrix_find(M, x):
            print x
    
  7. Daniel said

    Here’s another binary-search solution in Python. This one is O(n log m), but unlike my last solution it works (I hope).

    It iterates over the rows, performing binary search on each row.

    import numpy as np
    
    def matrix_find(matrix, element):
        for row in matrix:
            idx = np.searchsorted(row, element, side='right') - 1
            if idx > -1 and row[idx] == element:
                return True
        return False
    
    M = np.array([
        [ 1, 12, 43, 87],
        [ 9, 25, 47, 88],
        [17, 38, 48, 92],
        [45, 49, 74, 95]
    ])
    
    for x in range(-100, 100):
        if matrix_find(M, x):
            print x
    
  8. Paul said

    Two more solutions in Python. The second is a correct implementation of what Daniel tried to do with numpy in his first post, I think.

    def find_target(m, target):
        ncols = len(m[0])
        i, j = 0, ncols - 1
        while i < ncols and j >=0:
            if m[i][j] == target:
                return True
            i, j = (i+1, j) if m[i][j] < target else (i, j-1)
        return False
    
    def matrix_find(matrix, target):
        nrows, ncols = matrix.shape
        row, col = 0, ncols-1
        while row < nrows and col >= 0:
            elt = matrix[row, col]
            if elt == target:
                return True
            if elt < target:
                row += np.searchsorted(matrix[row:, col], target, side='left')
            else:
                col = np.searchsorted(matrix[row, :col], target, side='right') - 1
        return False
    
  9. Musicman said

    I’ve never used this website before, and i’m also fairly new to Programing. But this is my solution. Nested for loop that moves through the array until the value is found.

    //——————————————————
    // Consider a two-dimensional matrix
    //containing integer entries in which
    //all rows and all columns are sorted in ascending order
    //——————————————————
    var Matrix = [
    [1, 12, 43, 87],
    [9, 25, 47, 88],
    [17, 38, 48, 92],
    [45, 49, 74, 95]
    ];
    //——————————————————
    //Your task is to write a program that takes a matrix as
    //describe above, and a target integer, and determines
    //if the target integer is present in the matrix.
    //——————————————————

    var Target = 1;
    check: {
    for (var i = 0; i < Matrix.length; i++) {
    //console.log(Matrix.length[0]);
    for (var j = 0; j < Matrix[i].length; j++) {
    if (Matrix[i][j] == Target) {
    console.log("The Target is present in the Matrix, and is located at Matrix[" + i + ", " + j + "]");
    break check;
    }
    }
    }
    console.log("The Target is not present in the Matrix");
    }

  10. programmingpraxis said

    @Musicman: Welcome! We’re glad to have you.

    You might look at the menu bar for a description about how to format source code.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: