[解題筆記] Leetcode#74 — Search a 2D Matrix

Photo by Chris Ried on Unsplash

不了解Binary Search演算法，可以參考[演算法筆記] Binary Search文章

Problem

題號：Leetcode 74
標題：Search a 2D Matrix
演算法：Binary Search

Solution

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        var top = 0
        var bottom = matrix.count - 1

        //透過binary search，找出target落在哪一列(row)範圍
        while top <= bottom {
            let mid = (top + bottom) / 2
            if target < matrix[mid][0] {
                bottom = mid - 1
            } else if target > matrix[mid].last! {
                top = mid + 1
            } else {
                break
            }
        }

        if top > bottom {
            return false
        }

        let row = matrix[(top+bottom)/2]

        //透過binary search尋找此列(row)是否有target值
        var left = 0
        var right = row.count - 1

        while left <= right {
            let mid = (left + right) / 2
            if target > row[mid] {
                left = mid + 1
            } else if target < row[mid] {
                right = mid - 1
            } else {
                return true
            }
        }

        return false
    }
}