wayetan
12/29/2013 - 8:15 AM

## Search a 2D Matrix

Search a 2D Matrix

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int start_x = 0, start_y = matrix.length - 1;
int width = matrix[0].length;
int height = matrix.length;
// smaller than the smallest element or bigger than the biggest element
if(target < matrix[0][0] || target > matrix[height - 1][width - 1])
return false;
while(start_x < width && start_y >= 0){
if(matrix[start_y][start_x] < target)
start_x++;
else if(matrix[start_y][start_x] > target)
start_y--;
else
return true;
}
return false;
}
}
``````
``````/**
* Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
* -- Integers in each row are sorted from left to right.
* -- The first integer of each row is greater than the last integer of the previous row.
* For example,
* Consider the following matrix:
* [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
* Given target = 3, return true.
*/

public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int length = matrix.length;
int width = matrix[0].length;
int start = 0;
int end = width * length - 1;
while(start <= end){
int mid = (start + end) / 2;
int x = mid / width;
int y = mid % width;
if(matrix[x][y] == target)
return true;
else if(matrix[x][y] > target)
end = mid - 1;
else
start = mid + 1;
}
return false;
}
}``````