LINE BOT 開發紀錄 - 薪資級距確認篇(Binary Search)

本篇使用 JavaScript 來說明。

前言

最近在開發的 line bot 是讓使用者提供自己的薪資(target)，然後在我幫他確認完薪資級距後，提供該級距的相關資訊。「確認薪資級距」這個動作簡單來說，就是在一個「有序」數字陣列(numArray)中，找到使用者提供的薪資屬於這個陣列中的哪個區間?

在開始前有考慮過兩種搜尋法: Linear Search(線性搜尋)、Binary Search(二分搜尋)。考慮到基本工資以上的所有級距約有 50 個，Binary Search 會是個比較有效率的做法。之前在 CS50x 課程的 week0 有介紹二分搜尋法的概念，這次剛好可以來做個實踐。

Binary Search 實作

使用 Binary Search 要記得，它是針對「有序陣列」進行搜尋，所以開始之前要先幫陣列進行排序。

在陣列中尋找特定元素

Binary Search 是直接在陣列中搜尋特定元素。
因為是把陣列不斷切半再切半的尋找，而整個過程都是不斷重複的，所以這邊使用遞回函式(recusion)來完成。

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

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

LINE BOT 實作調整

針對薪資級距查詢有兩個需要調整的地方:

1. 薪資級距的套用有一個特性: 除了超過最高級距的狀況，套用的級距必須高於給定的薪資。
2. 給定的 target 即使不在 numArray 裡，最後也會回傳一個符合條件的數字。
   

首先，在切分 numArray 時，由於級距必須要比薪資高，所以 array.slice() 的起始點和結束點都需要調整，要從 middleIndex 再向後一位切起。

// target > numArray[middleIndex]
return binarySearch(numArray.slice(middleIndex + 1, numArray.length), target)

// target < numArray[middleIndex]
return binarySearch(numArray.slice(0, middleIndex + 1), target)

接下來，因為切分位置的改變，middleIndex 也需要調整。避免 numArray.length === 2 時，因為 numArray.slice(0, middleIndex + 1) ，造成陣列無法切小。

const middleIndex = Math.floor(numArray.length / 2) - 1

最後，設置遞迴的結束點: 當陣列不斷被切小後，只會剩下一個最終結果，只要把這個結果 return 就好。

if (numArray.length === 1) return numArray[0]

到目前為止其實已經確認可以得出正確級距，但是還有再優化的空間: 例如 target === numArray[middleIndex] ，依照目前邏輯還是必須切到剩最後一個才會 return ，會多出一些不必要的步驟。所以可以把這個狀況也加進遞迴停止條件中。最後的程式碼會是這個樣子:

function binarySearch (numArray, target) {
  const middleIndex = Math.floor(numArray.length / 2) - 1

  if (target === numArray[middleIndex]) return numArray[middleIndex]
  if (numArray.length === 1) return numArray[0]

  if (target > numArray[middleIndex]) {
    return binarySearch(numArray.slice(middleIndex + 1, numArray.length), target)
  } else  {
    return binarySearch(numArray.slice(0, middleIndex + 1), target)
  }
}

參考資料

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

文章內容如有錯誤，歡迎留言討論！