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

code-banner

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

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

二分搜尋法

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

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

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

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

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

-3-
[6] => 找到中位數 06 為目標值輸出索引 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;
}

留言

目前沒有留言。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *