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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
Output: false

Example 3:

Input: matrix = [], target = 0
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 0 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

# @lc code=start
using LeetCode

function search_matrix(matrix::Vector{Vector{Int}}, target::Int)::Bool
    m, n = length(matrix), length(matrix[1])

    (m == 0 || n == 0) && return false
    left, right = 1, m * n

    while left <= right
        mid = left + (right - left) ÷ 2
        num = matrix[mid ÷ n][mod1(mid, n)]
        if num == target
            return true
        elseif num < target
            left = mid + 1
        else
            right = mid - 1
        end
    end

    return false
end
# @lc code=end

search_matrix (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.