iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 23

Day23-搜尋法系列(二)-二分搜尋法

這次要介紹的是二分搜尋法(Binary Search),使用此排序法的話,要搜尋的資料列必須經過排序。運作原理就是將要尋找的值和資料列中間的值進行比較。
如果尋找的值比中間值小,就往左邊的子陣列再找中間值再做比較,直到找到值為止。
如果尋找的值比中間值大,就往右邊的子陣列再找中間值再做比較,直到找到值為止。

接著我們來實作吧!完成後會討論其時間複雜度~

  1. 先設定左邊界點和右邊界點的索引位置,並在左邊界點小於右邊界點的情況下設定中間值的位置。

  2. 開始將尋找值和資料列的值進行比較,若尋找值和中間值剛好相同,直接回傳中間值的索引位置,假如尋找值比中間值大時,讓中間值後的一個元素位置指定 left,在符合條件的狀況下重新執行 while 迴圈,再次取到新的中間值,然後不斷比較下去,直到找到和尋找值相同的值為止。

  3. 若都沒有找到和尋找值相同的值,就回傳 -1,程式結束。

function binarySearch(data, key) {
  let left = 0;
  let right = data.length -1;
  let middle;
  while(left <= right) {
    middle = Math.floor((left + right) / 2);
    if(data[middle] == key) {
      return middle;
    } else if(key > data[middle]) { // 尋找值比中間值大時,讓中間值後的一個元素位置指定left
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return -1;
}

時間複雜度:

  • 最佳時間複雜度:O(1)
    一開始資料列的中間元素就是我們想找的元素
  • 平均時間複雜度:O(log n)
  • 最差時間複雜度:O(log n)

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day23-binary-search.js

搜尋相關的兩個演算法都介紹完畢,從明天起將會介紹一些題目來做實作。


上一篇
Day22-搜尋法系列(一)-循序搜尋法
下一篇
Day24-動態規劃-0/1背包問題
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言