## Find Target In A Matrix

### August 1, 2017

Consider a two-dimensional matrix containing integer entries in which all rows and all columns are sorted in ascending order; for example:

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. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

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.

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.

Slightly more compact:

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.

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

My previous solution does not work.

The following example doesn’t find the 48.

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.

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.

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");

}

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

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