這題是搜尋矩陣(Matrix)尋找是否存在該值。
被列在「遞迴」的範圍內，所以用遞迴的方式解決。
該矩陣有一個特性，相同 y 或 相同 x 的欄列會照順序排。
得利用此特性來強化搜尋機制，不然硬方法全部遍歷(Traversal)一次就一定找得到。
按照前面的範例，選一個中間的點，該值小於目標值則捨棄右下方，該值大於目標值則捨棄左上方，然後遍歷同y或同x軸的元素。
如果只是單純的目標值小就往左上找，反之找右下，這樣是行不通的。
設想一下情境，找了一個元素，但不是目標值，接著就可以將矩陣切成四分，直接捨棄左上或右下的，剩下左下、右上及右下或左上的部分矩陣也需要尋找，於是最後會產生三個矩陣再繼續遞迴下去搜尋。
於是可以簡單地寫成：
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
def serach(yl, yu, xl, xu, target):
if yl > yu or xl > xu:
return False
xm = (xu-xl)//2 + xl
ym = (yu-yl)//2 + yl
if matrix[ym][xm] == target:
return True
elif matrix[ym][xm] > target:
# 往左下查詢
if serach(ym, yu, xl, xm-1, target): return True
# 往左上查詢
if serach(yl, ym-1, xl, xm-1, target): return True
# 往右上查詢
if serach(yl, ym-1, xm, xu, target): return True
else:
# 往右上查詢
if serach(yl, ym, xm+1, xu, target): return True
# 往右下查詢
if serach(ym+1, yu, xm+1, xu, target): return True
# 往左下查詢
if serach(ym+1, yu, xl, xm, target): return True
return False
if not matrix or not matrix[0]: return False
return serach(0, len(matrix)-1, 0, len(matrix[0])-1, target)
要注意不在左上與不在右下的差異，跟元素同x或同y座標的元素仍未被搜尋過，所以會被分給左下或是右上，因此兩者的右上、左下搜尋會有差異。
如果在搜尋的時候先把同x或同y座標的元素給找過，就可以再減少要搜尋的範圍。
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
def serach(yl, yu, xl, xu, target):
if yl > yu or xl > xu:
return False
xm = (xu-xl)//2 + xl
ym = (yu-yl)//2 + yl
#print(yl, yu, xl, xu)
if matrix[ym][xm] == target:
return True
elif matrix[ym][xm] > target:
# 往上，決定右上查詢範圍
yu2 = ym - 1
for y in range(yl, yu2+1):
if matrix[y][xm] == target:
return True
elif matrix[y][xm] > target:
yu2 = y - 1
break
if serach(yl, yu2, xm+1, xu, target):
return True
# 往左，決定左下查詢範圍
xu2 = xm - 1
for x in range(xl, xu2+1):
if matrix[ym][x] == target:
return True
elif matrix[ym][x] > target:
xu2 = x -1
break
if serach(ym+1, yu, xl, xu2, target):
return True
# 往左上方查詢
if serach(yl, ym-1, xl, xm-1, target):
return True
else:
# 往右，決定右上查詢範圍
xl2 = xm+1
for x in range(xl2, xu+1):
if matrix[ym][x] == target:
return True
elif matrix[ym][x] > target:
xl2 = x
break
if serach(yl, ym-1, xl2, xu, target):
return True
# 往下，決定左下查詢範圍
yl2 = ym+1
for y in range(yl2, yu+1):
if matrix[y][xm] == target:
return True
elif matrix[y][xm] > target:
yl2 = y
break
if serach(yl2, yu, xl, xm-1, target):
return True
# 往右下查詢
if serach(ym+1, yu, xm+1, xu, target):
return True
return False
if not matrix or not matrix[0]: return False
return serach(0, len(matrix)-1, 0, len(matrix[0])-1, target)
雖然這樣的寫法未必找得快，但是如果碰上要找重複幾個時候，只要改一改就能通用了。
雖然一開始的直覺是直接一個個搜尋，但是這樣就不合使用遞迴的期待。
更快的寫法是從左下開始搜尋，不斷往右上方逼進，最大次數就是長寬相加。這妥善利用該矩陣的特性，只是沒有遞迴。