[ Top Interview 150 ] 74. Search a 2D Matrix

문제

74. Search a 2D Matrix

  You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

  Given an integer target, return true if target is in matrix or false otherwise.

  You must write a solution in O(log(m * n)) time complexity.

• Input
  • 오름차순으로 정렬되어 있는 matrix (matrix를 위에서 부터 가로로 이어 붙였을 때 정렬되어 있음)
  • 찾는 원소 target
• Output : target이 matrix에 있는지 없는지를 반환
• Condition : Time complexity - O(log(M * N))
• Example
  • Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
  • Output: false

알고리즘 전략

• Binary Search

  • 정렬된 알고리즘에서 사용할 수 있는 Search Algorithm
  • 중간에 있는 원소와 찾고자 하는 원소의 크기를 비교한 후에, 그 결과에 따라 찾는 범위를 절반으로 줄이는 방법
  • Time complexity : O(logN)

• 해당 문제가 Binary Search가 어울리는 이유

  • 이미 "정렬"되어 있는 "1차원 배열"을 제공하였음
    • matrix가 2차원 배열이지만, 사실 가로로 이어붙이면 사싱 정렬되어 있는 1차원 배열로 간주하고 볼 수 있다.
  • 특정 원소가 들어갈 "위치를 찾아야함"
    • 이 문제에서는 해당 원소의 유무만을 판단하면 됨

• 기본 전략

  • matrix를 1차원 배열로 간주하기
    • 각각의 시작 pointer를 0, 와 끝 pointer를 matrix의 총 원소 크기로 설정
    • index를 0 부터 원소의 개수 - 1로 생각하며 matrix의 i번째 원소를 찾는 방법을 고안 (matrix[index / rowSize][index % rowSize]를 이용)
  • 기본적인 Binary Search를 이용하고, 해당 원소가 존재하지 않을 때까지 반복
    • 시작 pointer가 끝 pointer보다 뒤로갈 때까지 반복함

답안

• Complexity
  • Time complexity : O(log(N*M))
  • Space complexity: O(1)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        int front = 0;
        int behind = matrix.length * matrix[0].length - 1;

        while (front <= behind) {
            int middle = (front + behind) / 2;
            int middleValue = getElement(matrix, middle);

            if (target < middleValue) {
                behind = middle - 1;
            } else if (target > middleValue) {
                front = middle + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    private int getElement(int[][] matrix, int index) {
        int rowSize = matrix[0].length;
        return matrix[index / rowSize][index % rowSize];
    }
}