重念一次早該補起來的「資料結構與演算法」。這篇筆記下 Linear Search 和 Binary Search。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29766
本篇範圍：Chapter 1 ~ Chapter 3
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. 在 JavaScript 中，物件會轉換成 hashtable 的形式儲存。因此，Insert、Removal, Searching 和 Accessing 都是 O(1)
2. Array 的話，push-insert 會是 O(1)、unshift-insert 會是 O(n)、pop-removal 會是 O(1)、shift-removal 會是 O(n)、Searching 會是 O(n)、Accessing 會是 O(1)
Linear Search
Best – O(1)、Worst – O(n)、Avg – O(n/2)
|
1 2 3 |
for loop: if match target - return index return -1 |
Binary Search
Best – O(1)、Worst – O(log n)、Avg – O(log n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// sorted array // 拆一半 - 左右半： // 若 array 的中間項的值大於[要找的值]，代表[要找的值]在 array 的中間項左半 -> max = middle - 1 // 若 array 的中間項的值小於[要找的值]，代表[要找的值]在 array 的中間項右半 -> min = middle + 1 // 若 array 的中間項的值等於[要找的值]，return middle Psuedo Code: min = 0 max = arr.length - 1 while min <= max middle = (min+max)/2 if arr[middle] > num: max = middle - 1 else if arr[middle] < num: min = middle + 1 else return middle return -1 |
