# 演算法基本概念：Binary Search

###### tags: `Algorithms` `Back to Basics`

## 適用情況

在<span class="highlight">已排序的 array</span> 中搜尋指定數值的位置。

## 基本概念

最初將左右 pointers 設定在 array 兩端，計算兩 pointers 的中點。

如果中點數值大於指定搜尋的數值，代表指定數值會出現在左半邊，因此讓右 pointer 改指向（中點<span class="highlight">-1</span>），反之如果中點數值小於指定搜尋的數值則更新左 pointer 至（中點<span class="highlight">+1</span>）。

更新後繼續在左右 pointers 之間搜尋，直到中點數值等於指定數值，或左 pointer > 右 pointer（代表 array 不包含指定數值）。

這樣的搜尋演算法時間複雜度為 $O(log(n))$。

## 實作

Recursive 和 iterative 方法皆可。

## 中點的計算

計算中點時很直覺會想到將左右 pointers 代表的位置相加除以二，但實作上如果左右 pointers 分別都是很大的 integers，相加時可能會有溢出（overflow）的風險，也就是相加的結果會超出可用的位元數表示。

因此，比較可靠的做法是將左 pointer 代表的位置加上左右 pointers 間差值的一半：$left+(right-left)/2$。

另外，雖然先將左右 pointers 各自除以二再相加也可行，但這樣的經過兩次除法的做法會比較慢，因為乘除的運算速度比加減慢不少，且除的運算速度又比乘慢許多。

## 為何更新 pointer 時不是直接更新到中點？

1. 因為一定是在中點不等於指定數值時才會更新 pointer，既然中點不等於指定數值，在更新搜尋範圍時直接剔除中點是較有效率的。
2. 當 array 不包含指定搜尋數值時，搜尋結束條件是左 pointer > 右 pointer，如果在更新 pointers 時不排除中點的話會永遠達不到結束條件，設定其他結束條件也比較麻煩。

## 演算法比較

* Linear Search
* Time complexity：$O(n)$
* 適用於搜尋未排序的 array
* 如果搜尋目標常出現在接近 array 左端的位置，搜尋速度會加快許多
* 如果 array 有可能持續加入新的 element，這個做法也會較有效率，因為不用排序
* Binary Search
* Time complexity：$O(log(n))$
* 適用於搜尋已排序的 array
* 如果 array 有可能持續加入新的 element，會大幅影響效率，因為還需考慮排序花費的時間
* Hash Search
* Time complexity：$O(1)$
* Array 需要經過前處理轉換為 hash table，因此通常還需要考慮建表需花費的時間

## 多索引查詢（Search with multiple keys）

如果要應用 binary search 進行多索引查詢，一般來說有兩個主要的步驟：
1. 排序前處理：從最不重要的 key 開始排序（stable sort），依序排到最重要的 key。所謂重要性是指搜尋時的優先順序。例如排序年月日時，會先從日開始排序，接下來是月，最後是年。
2. Binary search：使用 binary search 從對後續搜尋結果最重要的 key 開始搜尋起，搜尋順序剛好和排序時相反。

## 參考資料

Data Structures and Algorithms 2019, NTUCS, 張智星

<style>
.highlight{
color: #F96870;
}
</style>