[LeetCode] 74. Search a 2D Matrix

轉自LeetCode

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.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

<Solution>

從題目知道，first col 和每個 row 是有排序的規則在

那麼就可以利用這一點

想法如下

• 看哪一個 first col 的元素 matrix[row][0] 是小於或等於 target 的，等於當然就回傳 true，小於就代表 target 會落在此 row

• 接著從該 row 的後面往前找，如果有找到就回傳 true，沒有就回傳 false

code 如下，O(mxn)

或者，可以針對 row 和 col 做兩次 binary search

這樣可以優化到O(logM + logN)

code 如下
c++

Kotlin