# 循序搜尋(Sequential Search)
定義：
* 一個一個依序搜尋，效率較差，但資料若未經排 序，僅能使用此方法
* 資料不需事先排序。
* N個資料，則搜尋比對的次數最少1次， 最多N次


# 二元搜尋(Binary Search)
* 定義：一種在已排序數列中尋找目標值的搜索算法
* 特性：
1. 資料必需事先排序。
1. N個資料，則搜尋比對的次數： 最少1次，最多Log2N次。
* 流程圖如下
* 

# 比較sequential search v.s. binary search

| Aspect | Sequential Search | Binary Search |
| ---------------- | ----------------------------------------------- | ---------------------------------------------------- |
| Time Complexity | O(n) | O(log n) |
| Space Complexity | O(1) | O(1) |
| Efficiency | Less efficient for large datasets | Highly efficient for large datasets |
| Search Method | Linear search: sequentially checks each element |Divides search space in half and eliminates one half |


# 氣泡排序(Bubble Sort)
* 定義：氣泡排序是一種簡單的排序算法，它反覆地走訪要排序的數列，依次比較兩個相鄰的元素，若是逆序則交換它們的位置，直到整個數列都是有序的

* 特性：
1. 一種穩定的排序算法，相同元素的相對位置在排序前後不會改變。
2. 在最壞情況下，氣泡排序的時間複雜度為O(n^2)，其中n是要排序的元素數目。


# 合併排序(Merge Sort)
* 定義：合併排序是一種分治法的排序算法，它將待排序數列不斷地分成較小的子數列，直到每個子數列只有一個元素，然後將這些子數列合併成較大的有序數列。

* 特性：
1. 無論是最好情況還是最壞情況，時間複雜度為O(n log n) 。這是因為合併排序採取devide and conquer方式排序，故時間複雜度都是線性的。
1. 它在合併操作中保持了相同元素的相對位置，因此是穩定的。

# 比較氣泡排序(Bubble Sort) v.s.合併排序(Merge Sort)

| 特徵 | 氣泡排序 | 合併排序 |
| -------- | -------- | -------- |
| 基本概念 | 反覆比較相鄰元素並交換 | 分治法，將數列分成子問題並合併 |
| 時間複雜度 | 最壞情況：O(n^2) | 始終為O(n log n) |
| | 最好情況：O(n) | |
| 穩定性 | 穩定 | 穩定 |
| 效率 | 效率較低，尤其在大型數列中 | 效率較高，特別在大型數列中 |


# 參考資料
1.Dr. Ana Bell , Prof. Eric Grimson, & prof. John Guttag. (2016, August). MIT6_0001F16_Searching and Sorting Algorithms. Introduction To Computer Science And Programming In Python. https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/resources/mit6_0001f16_lec12/