【Leetcode學習筆記】74. Search a 2D Matrix(Python Solution)

Keywords: Binary Search, Array

本題是 Binary Search 一個很不錯的延伸題型，會分成三個章節進行介紹

1. 題目 (中/英文說明、Examples、Constraints)
2. 題目解析 (Binary Search 演算法說明、解法思路)
3. 解法 (Codes)

題目 — LeetCode第74題：Search a 2D Matrix (Medium)

You are given an m x n integer matrix matrix with the following two properties:

    - Each row is sorted in non-decreasing order.
    - The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

題目是這樣的，給定一組二維矩陣 (matrix) 以及一個目標值 (target)。要求找出 target 是否存在於 matrix中。

※二維矩陣 (matrix) 是一組升序排列的陣列，具備以下特性：數字由左至右排序越來越大、由上至下越大 (可參閱 Example)。

※ 題目要求以「時間複雜度 O(log(m*n))條件」進行計算。

Example 1:

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

Example 2:

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

Constraints:

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

題目解析

• Brute Force (暴力解法)：若題目沒有規定時間複雜度，可直遍歷 matrix 中所有數值，直到找到target。而時間複雜度為 O(m * n)，其中m和n分別代表matrix的列與行長度。

# pseudo code 
row_len, col_len = len(matrix), len(matrix[0])

for row in range(row_len):
  for col in range(col_len):
    if matrix[row][col] == target:
      return True
return False

• Binary Search (二元搜尋)： 題目定義「矩陣是一個有序數組」並且查找目標值的「時間複雜度為 O(log(m*n))」，因此可以判斷使用Binary Search 演算法。

— — — —

甚麼是 Binary Search (二元搜尋)？

Binary Search (二元搜尋) 是一種在已排序的數組中，搜尋特定元素的搜尋演算法。核心概念是透過比較中間元素與目標元素大小，來不斷縮小搜尋範圍，最終找到目標元素或確定元素不存在。

我舉一個生活化的例子來說明：想像你在上課，老師告訴你要翻到課本的第140頁。你開始隨機翻閱課本，假設你先打開的是第183頁。當你看到這頁時，你馬上意識到目標頁數（第140頁）應該在當前頁數（第183頁）的左邊。於是，你知道你只需要在當前頁數的左半部分繼續尋找。這樣，你的搜索範圍就縮小到了第1頁到第182頁。

這就像是二分搜尋的過程，每次比較後，你都能將搜索範圍縮小一半，直到找到目標頁數為止。這種方法快速且高效，正是二分搜尋算法的核心思想。

為甚麼Binary Search的運算複雜度是 O(log n)?

Binary Search的運算複雜度為O(log n)，這是因為每次比較後，搜索範圍都會減半，這樣搜索過程是以對數 (logarithm)為基底的。具體來說，當你將n個元素縮減為n/2，再縮減為n/4，依此類推，直到搜索範圍縮小為1時，需要比較的次數是log2(n)。

我舉例一個例子來說明：假設你有一個已排序的數組，包含了16個元素： [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 30]，想要查找數字 3在這個數組中的位置。

1. 初始狀態： 數組：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 30]。 搜索範圍：整個數組，有16個元素。
2. 第一次比較： 中間元素是17。由於3比17小，所以你知道3應該在左半部分。現在搜索範圍：[1, 3, 5, 7, 9, 11, 13, 15, 17]
3. 第二次比較： 中間元素是9。由於3比9小，持續向左半部搜尋。現在搜索範圍：[1, 3, 5, 7, 9]
4. 第三次比較： 中間元素是5。由於3比5小，持續向左半部搜尋。現在搜索範圍：[1, 3, 5]
5. 第 四次比較：中間元素是3。你找到了目標值，搜索成功！

在這個例子中，初始時有16個元素。第一次比較後，搜索範圍減半為8個元素。第二次比較後，搜索範圍進一步減半為4個元素。這樣的過程持續下去，直到找到目標值。

這個例子中，16個元素 "最多需要" 4次比較就可以找到目標，而4=log₂(16)。故Binary Search的時間複雜度為O(log n)。

解法

v02 Binary Search

v01 Brute Force