74. Search a 2D Matrix

문제

https://leetcode.com/problems/search-a-2d-matrix/

코드

import java.util.*;

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int M = matrix.length;
        int N = matrix[0].length;
        int start=0;
        int end=M-1;
        int mid = 0;
        while(start < end){
            mid = (start+end)/2;

            if(matrix[mid][N-1] >= target){
                end = mid;
            }else{
                start = mid+1;
            }
        }

        int curRow = end;

        start = 0;
        end = N-1;


        while(start <= end){
            mid = (start+end)/2;
            if(matrix[curRow][mid] == target)
                return true;
            else if(matrix[curRow][mid] < target)
                start = mid+1;
            else if(matrix[curRow][mid] > target)
                end = mid-1;
        }


        return false;
    }
}

피드백

• upper bound를 사용함
  • lower_bound는 {min(x) | x >= k } 의 인덱스를 구하는 것이다.
  • upper_bound는 {min(x) | x > k } 의 인덱스를 구하는 것이다.
  • 헷갈리지 말자.