[LeetCode]Search a 2D Matrix

Search a 2D Matrix - LeetCode

풀이 생각

특징

• 각 row의 integers들은 left -> right로 오름차순 정렬되어있다.
• 각 row의 첫 번째 정수는, 이전 row의 마지막 정수보다 항상 더 크다.

구해야 하는것

• m x n matrix 내부에서, 값을 탐색하는 효율적인 알고리즘을 작성하라
  -> 탐색이 된다면 return "true"
  -> Otherwise return "false

생각 나는 것
1. row 들 끼리도 정렬되어있다 -> row들에 대한 이진탐색 -> matrix[i][0],matrix[i][n-1] 를 사용
2. row 자체가 정렬되어있다. -> 하나의 row에서 이진탐색

주어진 조건
1. row == m == matrix.length 인 m은 1이상 100이하
2. col == n == matrix[i].length인 n은 1이상 100이하

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