動機

leetcode時被弄過，所以記錄下來

問題

給定一個2d matrix，行與列都已排序好(小到大)，在這之中找出是否有指定的數字

1. 暴力

這沒有應用到已排序的特點，O(n^2)

def f(m,target):
  for x in m:
    for n in x:
      if n == target:
        return True
  return False

2. 分治

表格可以分開，又是表格， 同時分出來的表格都要走過(表格之間不會重疊)，最後再一起看有沒有目標，分治!! O(n^1.58)

def f(m,target,i=len(m)//2,j=len(m[0])//2):
  if not m:
    return False
  if m[i][j] == target:
    return True
  elif m[i][j] < target: # 在右手邊
    return f(m[i][j+1:],target) and # 右手邊
           f(m[i+1:],target) and # 下面
           f([x[j+1:] for x in m[:i]], target) # 上面的右手邊
  else: # 在左手邊
    return f(m[i][:j],target) and # 左手邊
           f(m[:i],target) and # 上面
           f([x[:j+1] for x in m[i+1:]], target) # 下面的左手邊

還記得two sum時怎麼移動ptr的嗎?

比目標大動右邊(範圍的上限變小)，比目標小動左邊(範圍的下限變大)

這裡也可以做出讓

  • 範圍的上限變小
  • 範圍的下限變大

的操作嗎?

從左下開始，如果

  • 太小，往右
  • 太大，往上

O(N+M)

def f(m,target):
  i = len(m)
  j = 0
  while 0 <= i and j < len(m[0]):
    if m[i][j] == target:
      return True
    elif m[i][j] > target:
      i -= 1
    else:
      j += 1
  return False

TODO

在functional pearl中其實有一篇說到怎麼從 分治 推到 saddleback search，但之後有時間再來看

Ref

saddleback Divide and Conquer