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;
    }
}