이진탐색(Binary Search)

문제출처 : https://leetcode.com/problems/search-a-2d-matrix/description/?source=submission-ac

 

다음 두가지 조건을 만족하는 m x n  integer matrix가 주어졌을 때, target이 matrix안에 있으면 true를 없으면 false를 리턴하라. 

(단, 시간복잡도 O(log(m*n))을 만족시켜라.)

 

조건 : 

1. 각 행의 숫자는 점점 커진다.

2, 각 행의 첫번째 숫자는 이전 행의 마지막 숫자보다 크다. 

 

제약사항:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

 

 

[Kotlin]

class Solution {
    lateinit var matGlobal: Array<IntArray>
    var targetG = 0
    var xLen = 0

    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        targetG = target
        matGlobal = matrix
        xLen = matGlobal[0].size
        return isItIn(0, xLen * matGlobal.size)
    }

    fun isItIn(st: Int, de: Int): Boolean {
        if(st + 1 == de) {
            if(matGlobal[st / xLen][st % xLen] == targetG) {
                return true
            }
            return false
        }

        var mid = (de - st) / 2 + st

        if(matGlobal[st / xLen][st % xLen] > targetG) {
            return isItIn(0, mid)
        } else if(matGlobal[st / xLen][st % xLen] < targetG) {
            return isItIn(mid, de)
        }

        return true
    }
}