[演算法] Binary Search：在陣列中尋找特定元素

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

問題描述

透過 binary search 的方式在一個陣列（numArray）中找出目標元素（target）：

function binarySearch(numArray, target) {...}

演算法實做

在 Big O Notation & Time Complexity 時，曾有使用 while 迴圈寫過一個 binary search 的函式。在這裡我們則要練習使用 遞回函式(recusion) 的方式來撰寫這個函式。

在使用遞回函式時有一個要注意的地方是， 當一個函式裡面呼叫另一個函式時，需要等待裡面的這個函式執行完後才會跳出來繼續執行原本函式的內容 ，因此在寫判斷式時需要特別留意執行的順序。

完整程式碼

在使用 Binary Search 時，記得要先將陣列元素排序。

function binarySearch (numberArr, target) {
  
  // 取得陣列中間的 index
  let middleIndex = Math.floor(numberArr.length / 2)
  
  // 如果找到就回傳 true
  if (numberArr[middleIndex] === target) {
    return true
  } 
  
  // 如果還沒找到，而且 numberArr 只剩一個元素，表示找不到
  if(numberArr.length === 1) {
    return false
  }

  // 如果還沒找到
  if (target > numberArr[middleIndex]) {
    // 且 target 大於中間的數值，則取後半段的陣列再搜尋
    return binarySearch (numberArr.slice(middleIndex, numberArr.length), target)
  } else if (target < numberArr[middleIndex]) {
    // 且 target 小於中間的數值，則取前半段的陣列再搜尋
    return binarySearch (numberArr.slice(0, middleIndex), target)
  } 
}

Algorith: Binary Search @ repl.it

資料來源

• Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy