# 搜尋演算法筆記
###### tags: `Algorithm`

### Sequential/linear Search 時間複雜度為O(1)
(1) 資料搜尋之前無需事先排序

(2) 資料存於 sequential access (比如鏈結串列) 或 random access (比如陣列) 機制皆可支持。

### Binary Search 時間複雜度為O(log n)
(1) 資料必須事先由小到大排序好

(2) 資料是用 random access 機制 (例如 Array) 存放才可支援。

資料量少時，使用 linear search 即可；資料量大時使用 Binary Search

1. 基本概念
https://kopu.chat/2017/08/04/%e6%90%9c%e5%b0%8b%e8%88%87%e6%8e%92%e5%ba%8f-search-sort/

2. 二元搜尋之五大類題型
https://www.cnblogs.com/grandyang/p/6854825.html
## Graph

### Depth-First Search
1. 儘可能的深度搜索，直到該節點的所有邊上節點都已探尋；就回溯(backtracking)到前一個節點，重覆探尋未搜尋的節點。
若從出發節點到所有搜尋節點都為結束時，要確認是否遍尋過所有節點?若還有未遍尋節點，則隨機挑選一個做為出發節點，重複上述步驟，直到找到目的節點或遍尋全部節點。
3. 盲目搜索(uninformed search)是利用Stack來處理(先進後出)，通常以遞迴的方式呈現。
4. 會用到的工具:
* Color:用來區分節點狀態。未走過:白色、走過:灰色、結束:黑色
* Predecessor:陣列型式，用來回溯路徑，可以設定-1代表起點
* Discover:紀錄已發現的節點
* Finish:紀錄死路的節點
* Depth-First Tree:Predecessor Subgraph (出發節點有幾個就有幾棵樹)
5. Reference:
a)https://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html
b) http://simonsays-tw.com/web/DFS-BFS/DepthFirstSearch.html

### Breadth-First Search
1. 各個node相對於root有其對應的level，按照level由小到大依序對node進行Visiting。
2. 通常用Queue來實作(先進先出)。先以root為起點，找出所有相鄰最小level的節點，並移入Queue，接著將root從queue移除，以倒數第一個點作為起點重複上一步，直到將所有點從Queue移除，就遍尋完成整個Graph。
3. 會用到的工具:
* Distance:用來記錄起點和節點間的距離，也就是遍尋同個level節點時的依據
* Color:用來區分節點狀態。未走過:白色、走過:灰色、結束:黑色
* Predecessor:陣列型式，用來回溯路徑，可以設定-1代表起點
4. Reference:
a)
https://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html
b) https://blog.techbridge.cc/2019/12/21/leetcode-%E5%88%B7%E9%A1%8C-pattern-breadth-first-search/

### DFS & BFS difference
https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

**NOTE:**
* 很多時候能用DFS解的題目，通常也能用BFS解