07.08.2023
74. Search a 2D Matrix medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/301
Problem TLDR
2D Binary Search
Intuition
Just a Binary Search
Approach
For more robust code:
inclusive
lo
andhi
the last condition
lo == hi
move borders
lo = mid + 1
,hi = mid - 1
check the result
use built-in functions
Complexity
Time complexity:
O(log(n∗m))Space complexity:
O(1)
Code
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
var lo = 0
var hi = matrix.lastIndex
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
val row = matrix[mid]
if (target in row.first()..row.last())
return row.binarySearch(target) >= 0
if (target < row.first()) hi = mid - 1 else lo = mid + 1
}
return false
}