0074. Search a 2D Matrix (Medium)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

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

1
2
3
4
5
6
7
8

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

Example 2

1
2
3
4
5
6
7
8

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

分析/解題

給定一個m x n的矩陣，此矩陣每列(row)都是從左到右升冪排序；
同時此矩陣每列的第一個值都比前一個列的最後一個值還要大。
試找出一個有效率的演算法，
來處理在這個矩陣搜尋一個值是否在這裡面。

有沒有覺得很熟悉？
其實這題的延伸題目就是上一題，作為同樣Medium難度的題目，
這題就要來得簡單許多。
為什麼呢？
因為按照題目的定義的話，
我們假設從每一列的尾巴接到下一列的頭，
最終就會得到一個完整的已排序陣列。
那麼，已排序陣列的搜尋方式，
我們以前已提到過了，就使用基本的二元搜尋法(Binary Search) 即可。
(還沒弄清楚或還不知道二元搜尋法的讀者，可以參見前面這篇 。)

那麼我們所要做的，就只剩下將matrix上的index，
轉為如果攤平以後對應到的陣列index即可。
對於matrix[i][j]來說，
由於有m列n行，i代表從0到i(總共i+1個列) ，
所以前面會經過i列，共 (i * n) 個數字；
接著要往右邊移動，
j代表從0到j有j+1個數字 ，再相加起來，
所以matrix[i][j]是整個攤平以後的第(i * n + j + 1)個數字，
從0開始起算的話就是(i * n + j)。

因此，如果我們找到某一個中間index mid ，
要轉換成i, j 的型式的話，
就只需要分別取除以n得到的商和餘數 即可。

依此進行二元搜尋的時候，其方式就和一般的二元搜尋一模一樣，
若跳出迴圈則代表該目標值不存在於matrix中，則回傳false 。

Java

Python的部分請不要忘記取整數除法要用雙斜線"//"。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(log(mn))/O(1))

相似及延伸

1. 0240. Search a 2D Matrix II (Medium)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~