ค้นหาในเมทริกซ์ 2D แบบ Sorted (Search a 2D Matrix II) ใน Python

เมทริกซ์ m×n ที่แถวและคอลัมน์เรียงลำดับจากน้อยไปมาก ค้นหา target อย่างมีประสิทธิภาพ

ตัวอย่างเมทริกซ์

[[1,  4,  7, 11, 15],
 [2,  5,  8, 12, 19],
 [3,  6,  9, 16, 22],
 [10, 13, 14, 17, 24],
 [18, 21, 23, 26, 30]]

target=5 → True, target=20 → False

อัลกอริทึม: เริ่มจากมุมขวาบน (หรือซ้ายล่าง)

1. เริ่มที่ (row=0, col=last)
2. ถ้าเจอ target → True
3. ถ้าค่าปัจจุบัน > target → ไปซ้าย (col--)
4. ถ้าค่าปัจจุบัน < target → ไปล่าง (row++)
5. ออกขอบเมทริกซ์ → False

โค้ด

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        rows, cols = len(matrix), len(matrix[0])
        r, c = 0, cols - 1  # มุมขวาบน
        
        while r < rows and c >= 0:
            val = matrix[r][c]
            if val == target:
                return True
            elif val > target:
                c -= 1
            else:
                r += 1
        return False

# ทดสอบ
mat = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
sol = Solution()
print(sol.searchMatrix(mat, 5))   # True
print(sol.searchMatrix(mat, 20))  # False

ความซับซ้อน

• Time: O(m + n)
• Space: O(1)

สรุป

กำจัดหนึ่งแถวหรือคอลัมน์ต่อรอบ ได้คำตอบเร็วกว่า binary search ทุกแถว