問題

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

方法

binary searchの感じで近づいた。

#1: 分かりやすいけどコードが長くなる方法

１。行(row)についてバイナリサーチを行なってターゲットがありそうな行を選ぶ。
２。列(col)についてバイナリサーチをもう一度行なってターゲットの数字と一致する元素があるか確認する。

#2: もっとコードが短くなる方法

１。二次元配列について、(0,0)の位置をleftに設定する
２。二次元配列について、(m-1,n-1)の位置をrightに設定する。
３。二次元配列を線形配列（一次元)と思い、バイナリサーチ行う。

具現 (Java)

class Solution {
    
    public boolean searchMatrix(int[][] matrix, int target) {
        
        final int r = matrix.length;
        final int c = matrix[0].length;
        
        int top = 0, bottom = r-1, pivot = (top+bottom)/2;
        
        while (top < bottom) {
            
            if (matrix[pivot][0] <= target && target <= matrix[pivot][c-1]) break;
            
            else if (matrix[pivot][c-1] < target) top = pivot+1;
            else /* matrix[pivot][0] > target */ bottom = pivot-1;
            
            pivot = (top+bottom)/2;
        }
        
        int left = 0, right = c-1, center = (left + right)/2;
        
        while (left < right) {
            
            if (matrix[pivot][center] == target) return true;
            
            else if (target < matrix[pivot][center]) right = center-1;
            else /* matrix[pivot][center] < target*/ left = center+1;
            
            center = (left+right)/2;
        }
        
        return matrix[pivot][center] == target;
    }
}

class Solution {
    
    public boolean searchMatrix(int[][] matrix, int target) {
        
        final int col = matrix[0].length;
        
        int left = 0;
        int right = matrix.length * col - 1;
        int pivot = (left + right) / 2;
        
        while (left < right) {
            
            final int y = pivot / col;
            final int x = pivot % col;
            
            if (matrix[y][x] == target) return true;
            
            else if (target < matrix[y][x]) right = pivot - 1;
            else /* matrix[y][x] < target*/ left = pivot + 1;
            
            pivot = (left + right) / 2;
        }
        
        return matrix[pivot / col][pivot % col] == target;
    }
}