Binary Search 二元搜尋常見問題

Binary Search 二元搜尋常見問題
Categories:
Tags:

中間指標切分點算法

索引 0 1 2 3 4 5 6 7 8 9
指標位置 左指標 右指標

取中間偏左的數字

  • 中間指標 左方數字 個數 小於或等於 右方數字 個數

公式：

  • (左指標 + 右指標) / 2，無條件捨去
  • 左指標 + (右指標 - 左指標) / 2，無條件捨去
// 公式 1
let middleNumberPointer = Math.floor((rightNumberPointer + leftNumberPointer) / 2);
// 公式 2
let middleNumberPointer = leftNumberPointer + Math.floor((rightNumberPointer - leftNumberPointer) / 2);

偶數陣列

中間指標 左方數字 個數 小於 右方數字 個數

e.g. [0,1,2,3,4,5,6,7,8,9]

  • (0 + 9) / 2 = 4.5，無條件捨去為 4
  • 0 + (9 - 0) / 2 = 4.5，無條件捨去為 4
索引 0 1 2 3 4 5 6 7 8 9
指標位置 左指標 中間指標 右指標

奇數陣列

中間指標 左方數字 個數 等於 右方數字 個數

e.g. [0,1,2,3,4,5,6,7,8]

  • (0 + 8) / 2 = 4，無條件捨去為 4
  • 0 + (8 - 0) / 2 = 4，無條件捨去為 4
索引 0 1 2 3 4 5 6 7 8
指標位置 左指標 中間指標 右指標

while 迴圈判斷式 left <= right

區間定義

索引 0 1 2 3 4 5 6 7 8 9 說明
[3, 5] 閉區間 3 4 5 閉區間 [x, y]：包含 x, y
(4, 9) 開區間 5 6 7 8 開區間 (x, y)：不包含 x, y
[1, 6) 左閉右開區間 1 2 3 4 5 左閉右開區間 [x, y)：包含 x, 不包含 y

Binary Search 的寫法中的 left 與 right 代表的就是：答案還有可能存在的區間的兩端點，這是個 閉區間 [x, y]

所以當 left == right 的時候，代表可能答案會在 [3,3] 之間，且區間裡只有 1 個元素，但不確定這個元素是不是要找的答案，所以要再判斷一次

因此 while 的判斷式會是 <= 而非 <。

中間指標移動方式，為什麼是 right = mid - 1 跟 left = mid + 1

因為我們要的答案是 閉區間，假如 mid 不是答案，那 mid 必須被排除，需要直接捨棄

當要的答案在左側，則會用 [left, mid-1] 當作新的區間，左邊指標不動，移動右側指標

當要的答案在右側，則會用 [mid+1, right] 當作新的區間，右邊指標不動，移動左側指標

參考資料