[LeetCode]Search a 2D Matrix

Search a 2D Matrix - LeetCode
草の考え
特長
各行

の整数は、左->右の順に並べられます.

各行の最初の整数は、常に前の行の最後の整数より大きい.

必要

m x n行列の内部で,効率的な探索値アルゴリズムを記述した.
->に移動すると「true」に戻ります
-> Otherwise return "false

思い出す
1.row間でもソートが行われている->rowに対してバイナリサーチを用いる->マトリクス[i][0]、マトリクス[i][n-1]
2.row自体が整列している->1行でバイナリ・ナビゲーション
与えられた条件
1. row == m == matrix.長さが1以上100以下のm
2. col == n == matrix[i].長さが1以上100以下のn

class Solution {
     /*
        특징
        - 각 row의 integers들은 left -> right로 오름차순 정렬되어있다. 
        - 각 row의 첫 번째 정수는, 이전 row의 마지막 정수보다 항상 더 크다. 
        
        구해야 하는것 
        m x n matrix 내부에서, 값을 탐색하는 효율적인 알고리즘을 작성하라
        -> 탐색이 된다면 return "true"
        -> Otherwise return "false"
        
        생각 나는 것 
        1. row 들 끼리도 정렬되어있다 -> row들에 대한 이진탐색 -> matrix[i][0] 를 사용
        2. row 자체가 정렬되어있다. -> 하나의 row에서 이진탐색 
        
        주어진 조건 
        1. row == m == matrix.length 인 m은 1이상 100이하
        2. col == n == matrix[i].length인 n은 1이상 100이하 
        */
    public int m,n;
    public boolean searchMatrix(int[][] matrix, int target) {
        boolean ans = false; 
        int r; 
        m = matrix.length;
        n = matrix[0].length;
        if( m == 1 ){
            ans = binSearch(matrix,target,0);
        }else{
            r = rowBinSearch(matrix,target);
            if(r == -1) ans = false;
            else ans = binSearch(matrix,target,r);
        }
        return ans; 
    }
    
    // target이 들어있는 row 가 몇 번째 row인지 return한다. 
    public int rowBinSearch(int[][] matrix, int target){
        int left = 0, right = m-1;
        // matrix[i][0]
        int mid = -1; 
				// 종료 condition이 필요 
        while(left<=right){
            mid = (left+right)/2;
						// 특정 row를 찾는 것은, target이 해당 row의 [0]와 [n-1] 범위 값 사이에 있음됨
            if(matrix[mid][0] <= target && matrix[mid][n-1] >= target) return mid; 
            else if(matrix[mid][0] > target){
                right = mid-1;
            }
            else if(matrix[mid][n-1] < target){
                left = mid + 1; 
            }
        }
				// 범위를 완전히 벗어나는 경우 -> row 탐색부터, 탐색할 수 없음을 찾은 경우 
        return -1; 
    }
    // 특정 row에서 binSearch
    public boolean binSearch(int[][] matrix, int target, int row){
        int left = 0, right = n-1;
        int mid = 0 , preMid = -1 ;
        while(left<=right){
            mid = (left+right)/2; 
            if( mid == preMid)break;
            if(matrix[row][mid] == target) {
                return true;
            }
            else if(matrix[row][mid] > target ) right = mid - 1; 
            else if(matrix[row][mid] < target ) left = mid + 1; 
            preMid = mid; 
        }
        return false; 
    }
    
}