Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


搜尋演算法 1 - Linear Search / Sequential Search

By Jimmy 2022-04-25
發表於 演算法 資工
搜尋演算法 1 - Linear Search / Sequential Search

Linear search (線性搜尋),又稱為 sequential search,是最基本的搜尋演算法,通常用來搜尋尚未排列的資料。

1. Linear Search 原理解釋

Linear search 的原理很直觀:一個一個搜尋,搜尋到目標元素的話就 return,因此時間複雜度是 O(n)。

2. JavaScript 實作

迭代整個陣列,如果有找到目標元素,則 return 目標元素的 index 值,沒有的話則 return -1:

function linearSearch(arr, target) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

3. Time Complexity

最佳:O(1)
最差:O(n)
平均:O(n)

4. 參考資料

大話資料結構(全新彩色版)


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More