problem

輸入為一個 m * n 的雙層陣列和一個目標整數 target。陣列中的元素皆不重複，且每一列和每一欄都由小到大排序。如果 target 有在陣列中，回傳列和欄的索引，否則回傳 [-1, -1]。

sample input:
matrix = [
 [1, 4, 7, 12, 15, 1000],
 [2, 5, 19, 31, 32, 1001],
 [3, 8, 24, 33, 35, 1002],
 [40, 41, 42, 44, 45, 1003],
 [99, 100, 103, 106, 128, 1004]
]
target = 44

sample output:
[3, 3]

這類在陣列中尋找目標數字的題目，當然還是可以用遍歷陣列的方式來搜尋，但這樣會需要 m * n 時間。

考慮到列和欄皆為有序，可以利用元素和目標數字相比的結果，來排除一整列或一整欄的數字，加快搜尋的速度，具體的作法是：

1. 將最右上角的數字 num 與 target 相比，若 num > target，則代表 num 下方同一欄的數字一定都大於 target，可以被排除。因為同一欄的數字已被排除，所以接下來將 num 更新為左邊的數字，繼續比較。
   以範例輸入來說，1000 > 44，所以排除所有 1000 下方的數字，接下來將 num 更新為 15。
   1,   4,   7,   12,  15,  1000
   2,   5,   19,  31,  32,  1001
   3,   8,   24,  33,  35,  1002
   40,  41,  42,  44,  45,  1003
   99, 100, 103, 106, 128, 1004
2. 若 num < target，則 num 左方同一列的數字都會小於 target，可以被排除。接著更新 num 為下方的數字，重複比較的步驟。
   例如此時 15 < 44，代表比 15 小的都可以排除，接下來以 32 和目標比較。
   1,   4,   7,   12,  15,  1000
   2,   5,   19,  31,  32,  1001
   3,   8,   24,  33,  35,  1002
   40,  41,  42,  44,  45,  1003
   99, 100, 103, 106, 128, 1004

   32 < 44，一樣 32 左方的數字都可以排除，接下來 num 更新為 35，以此類堆。
   1,   4,   7,   12,  15,  1000
   2,   5,   19,  31,  32,  1001
   3,   8,   24,  33,  35,  1002
   40,  41,  42,  44,  45,  1003
   99, 100, 103, 106, 128, 1004

3. 比較的過程中如果碰到 num == target，則回傳索引值，否則最終回傳 [-1, -1]。

若 m, n 為陣列的寬與長，
time: O(m + n) 因為每次更新 num 為左方或下方數字，直到看完整個陣列至多會更新 (m + n) 次。
space: O(1)

function searchInSortedMatrix(matrix, target) {
  let row = 0;
  let col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] > target) {
      col--;
    } else if (matrix[row][col] < target) {
      row++;
    } else {
      return [row, col];
    }
  }
  return [-1, -1];
}