Search a 2D Matrix

问题：

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.

思路：

　　二分查找

我的代码：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)   return false;
        int row = matrix.length;
        int col = matrix[0].length;
        int[] cols = new int[row];
        for(int i = 0; i < row; i++)
        {
            cols[i] = matrix[i][0];
        }
        int rowIndex = getIndex(cols, target);
        if(rowIndex < 0)    return false;
        int[] rows = new int[col];
        for(int i = 0; i < col; i++)
        {
            rows[i] = matrix[rowIndex][i];
        }
        int colIndex = getIndex(rows, target);
        return rows[colIndex] == target ? true : false;
    }
    public int getIndex(int[] array, int target)
    {
        int left = 0;
        int right = array.length - 1;
        while(left <= right)
        {
            int mid = (left + right)/2;
            if(target == array[mid])
            {
               return mid; 
            }
            else if(target > array[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}

View Code

他人代码：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        int num = rows * cols;
        
        int left = 0;
        int right = num - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            int row = mid / cols;
            int col = mid % cols;
            
            int n = matrix[row][col];
            
            if (n == target) {
                return true;
            } else if (n < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;        
    }
}

View Code

学习之处：

　　他人代码的思路更加简洁，把整个矩阵看成一个Array，好想法，rowNum = num/row colNum = num % col 思路实在是妙