74. Search a 2D Matrix

문제 설명

Write an efficient algorithm that searches for a value in an m x n 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.
행렬에서 target 이 있는지 판별하는 문제이다.

Example

> 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

Idea

우선 이 문제의 조건은 각 행의 숫자가 오름차순으로 정렬되어있고 각 행의 마지막 숫자는 다음 행의 첫 숫자보다 낮게 정렬되있다. 그래서 target값을 찾는데 이진탐색을 이용했고
n차원 배열로 되어있는 matrix값을 flat 메소드를 이용해 1차원 배열로 변환하여 쉽게 값을 찾아냄

Solution

var searchMatrix = function(matrix, target) {
    matrix = matrix.flat()
    let left = 0
    let right = matrix.length-1
    while(left<=right){
        const mid = Math.floor((left+right) / 2)
        if(matrix[mid] === target) return true
        matrix[mid] > target ? right= mid-1 : left = mid+1
    }
    return false
};