Created
March 7, 2015 23:43
-
-
Save graemeboy/62d411e1b5cc29a77121 to your computer and use it in GitHub Desktop.
2D Ordered Matrix Search
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| var matrix = [ | |
| [1, 1, 1, 2, 2, 3], | |
| [2, 3, 3, 4, 4, 6], | |
| [3, 5, 6, 6, 7, 7], | |
| [4, 5, 6, 6, 8, 8], | |
| [5, 7, 7, 8, 8, 9] | |
| ]; | |
| var target = 6; // We’re going to try find the position of 6 in the array | |
| function matrixFind (matrix, target) { | |
| var x = 0; // Position from left-side of the matrix | |
| var y = matrix.length - 1; // Position from top of matrix; | |
| var steps = 0; // Count the number of steps to measure efficiency. | |
| // We start at the top and traverse down to the start of the matrix | |
| while (y >= 0 && x < matrix[y].length) { | |
| steps += 1; | |
| if (matrix[y][x] > target) { | |
| y--; | |
| } else if (matrix[y][x] < target) { | |
| x++; | |
| } else { // matrix[y][x] == target | |
| return new Array(y,x,steps); | |
| } | |
| } | |
| return -1; // Did not find target in matrix | |
| } | |
| var ans = matrixFind(matrix, target); | |
| if (ans.length > 2) { | |
| console.log(target + " found at matrix["+ans[0]+"]["+ans[1]+"]" + ". Found in " + ans[2] + " steps"); // returns [3,2] | |
| } else { | |
| console.log("Target not found in matrix"); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment