iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 22
1
Software Development

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

Day22-搜尋法系列(一)-循序搜尋法

今天要介紹的是循序搜尋法(Sequential Search),也可稱為線性搜尋法(Linear Search),運作原理相當簡單,就是在資料列一個一個值的和目標值做比對,直到找到為止。

此網頁有小動畫可以參考看看,非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Search/LinearSearch/LinearSearch.php

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

function linearSearch(data, key) {
  let index = 0;
  while (index < data.length) {
    if (data[index] == key) { // 某元素值和key查找值相同,回傳目前索引
      return index;
    }
    index++;
  }
  return -1;
}

時間複雜度:

  • 最佳時間複雜度: O(1)
    第一個走訪到的元素就是我們想找的元素
  • 平均時間複雜度: O(n)
  • 最差時間複雜度: Ο(n)
    最後一個走訪到的元素才是我們想找的元素

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

明天將會介紹第二種搜尋演算法-二分搜尋法!


上一篇
Day21-排序法系列(五)-快速排序法
下一篇
Day23-搜尋法系列(二)-二分搜尋法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言