[GreatFrontEnd題目] Binary Search 二分搜尋法(JS)

1 年前

內容目錄 隱藏

https://www.greatfrontend.com/questions/javascript/binary-search

Implement a function that performs binary search on an array of numbers. The function should take in a sorted array of integers and a target integer to find. It returns the index of the target element or -1, if the target element doesn’t exist in the array.

Examples

binarySearch([1, 2, 3, 6, 9, 11], 6); // 3
binarySearch([1, 2, 3, 12, 16, 14], 5); // -1

這題就是用二分搜尋法找出目標的值在陣列中的索引。

二分搜尋法

首先要先知道二分搜尋法是怎麼樣進行搜索的：

找出當前陣列的中位數(陣列長度/2)，若陣列長度為奇數則除以2後無條件捨去或進位都可以。比方說長度為 5，那麼中位數可以是第 2 或第 3 個數。
比較目標值與中位數的大小，若目標值 > 中位數，則代表目標值在中位數右側，反之目標值則在左側。判斷出目標值在左側還是右側後，將目標值(含)另一側的數全部捨棄不看。
剩餘的數再重複執行以上兩個步驟直至找到目標數或者找完所有數（可能找不到目標值）。

以範例的輸入為例，要在 [1, 2, 3, 6, 9, 11] 中找到 6 的索引，使用二分搜尋法的過程即為：

-0--1--2--3--4---5-
[1, 2, 3, 6, 9, 11] => 找到中位數 3，6 比 3 大所以捨棄中位數(含)左半邊的數

-3--4---5-
[6, 9, 11] => 找到中位數 9，6 比 9 小所以捨棄中位數(含)右邊的數

-3-
[6] => 找到中位數 0，6 為目標值，輸出索引 3

Solution

循環終止條件設為 startIndex <= endIndex，只要 startIndex 小於等於 endIndex 就繼續，如果找不到目標值的話最終 startIndex 會大於 endIndex
獲取中位數索引的方式： Math.floor((endIndex + startIndex) / 2)
endIndex = midIndex - 1; 和 startIndex = midIndex + 1; 這邊中位數 +1, -1 是為了下一輪比較時不重複判斷中位數，如果中位數是要找的值的話會符合的是第一個判斷式 if (arr[midIndex] === target)

export default function binarySearch(arr, target) {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((endIndex + startIndex) / 2);
    if (arr[midIndex] === target) {
      return midIndex;
    } else if (arr[midIndex] > target) {
      endIndex = midIndex - 1;
    } else {
      startIndex = midIndex + 1;
    }
  }

  return -1;
}