---
title: 'Search - 搜尋'
disqus: hackmd
---
[TOC]

## Search - 搜尋

* 搜尋方式
* Internal Searching (內部搜尋)：可將資料一次置於 RAM
* External Searching (外部搜尋)：需透過 Disk 協助存取資料
* 資料狀態
* Static (靜態)：資料固定
* Dynamic (動態)：更動頻繁、無法預知

---

### Linear Search - 線性搜尋
* 不須事先排序
:::warning
**Time Complexity：**
設有 n 筆資料，平均次數為：第 1 次搜尋成功 + 第 2 次搜尋成功 + ... 第 n 次搜尋成功

＝ $\dfrac{(1+n)n}{2}*\dfrac{1}{n}=O(n)$
:::

---

### Binary Search - 二分搜尋

* 須事先排序
* 資料必須可以 Direct Access、Random File
:::warning
**Time Complexity：**
設有 n 筆資料，每一次選中間值判斷：$\dfrac{1}{2}*n$

比較次數：$\lceil log_2(n+1)\rceil$ ＝ $O(log_2n)$
:::

:::warning
**Time Complexity (Recursive)：**

設 $T(n)$ 為在 n 筆資料搜尋之時間函數，$T(1)=1$ ，1 筆資料的搜尋時間為 1

則每回合 $T(n)=T(\dfrac{n}{2})+1$ ，每搜尋一次資料量減半、時間單位+1

＝ $T(\dfrac{n}{2})+1$ + $T(\dfrac{n}{2^2})+2$ + ... + $T(1)+log_2n$

＝ $O(log_2n)$
:::

:::warning
**Time Complexity (Master Theorem)：**
Master Theorem：$T(n)=aT(\dfrac{n}{b})+f(n)，a\ge1,b>1$
根據上述：$T(n)=T(\dfrac{n}{2})+1，a=1,b=2$
<br>
代入 $n^{log_b^a}=n^{log1}=n^{0}=1=f(n)$
<br>
則 $T(n)=\theta(1*log_2n)=\theta(log_2n)$

:::
---

### Fibonacci Search - 費氏搜尋

---

### Interpolation Search - 插補搜尋

###### tags: `Data Structure`