iT邦幫忙

2022 iThome 鐵人賽

DAY 10
0
Software Development

刷題也算一種電競吧:演算法與資料結構系列 第 10

Day 9 絕命雙排 - Linear Search & Binary Search

  • 分享至 

  • xImage
  •  

Linear Search

Linear Search 非常常見,甚至在學迴圈時就已經用過了。以下直接給範例練習!

Practice - Linear Search

給定一個數字陣列 array 與一個數字 n,求出 n 是否在 array 中。回傳 truefalse。

function linearSearch(array, n){
for (let i = 0; i < array.length; i++) {
    if (n === array[i]) {
        return true
    }
}
return false;
}

最基本的搜尋方式,耗費的時間隨著輸入的資料而增長,時間複雜度為 O(n)。

Binary Search

Binary Search 是一種更快的搜尋方式,比起 Liner Search 每次查找時只會排除一個元素,Binary Search 每次查找比對後可以排除掉當前資料量的一半元素。但 Binary Search 只能用在排序過的資料。

先前 Day 7 - Divide and Conquer 章節有提到過,可回去複習後實作以下練習。

Practice 1 - Binary Search

給定一個已排序過的數字陣列 array 與一個數字 n,求出 n 是否在 array 中。回傳 truefalse。

function binarySearch(array, n){
let start = 0,
  end = array.length - 1,
  middle = Math.floor(array.length / 2);

while (start <= end) {
  if (array[middle] === n) {
      return true;
  } else if (array[middle] > n) {
      end = middle - 1;
  } else {
      start = middle + 1;
  }
  middle = Math.floor((start + end) / 2);
}

return false;
}

Binary Search 時間複雜度為 O(log n)

每次比對時,排除一半元素。若陣列有 32 個元素,最差的情況會比對 5 次。若陣列有 128 個元素,最差的情況會比對 7 次。

在輸入資料增長的情況下,Binary Search 所需比對的次數增長幅度少很多。


上一篇
Day 8 BO5-5 - Recursion
下一篇
Day 10 還敢下來啊 - Bubble Sort
系列文
刷題也算一種電競吧:演算法與資料結構34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言