# What is Binary Search?
Binary Search 是一種用來搜尋 "**排序**" 陣列的搜索演算法。其搜索方式則是使用陣列接近中間點的數字(Array[mid])，將陣列分成兩半個數接近的子陣列，再透過此數字決定出欲搜索的數字可能在哪個子陣列，接著再選取此子陣列中接近中間點的數字(subArray[mid])，將此子陣列分成更小的兩個子陣列，並透過此數字決定要搜尋哪個更小的子陣列，以區間套的方式逐步迭代，進而搜尋目標數字是否存在於陣列中，如下圖所示 :arrow_down:
<a href="https://en.wikipedia.org/wiki/Binary_search_algorithm#/media/File:Binary-search-work.gif">
<img src="https://upload.wikimedia.org/wikipedia/commons/c/c1/Binary-search-work.gif">
(Source:https://upload.wikimedia.org/wikipedia/commons/c/c1/Binary-search-work.gif)</a>
# Implement
接下來就簡單讓我們看一下 Binary Search 如何實做吧，實作方式可以分為使用迴圈的 "**迭代版本**" 以及使用遞迴的 "**遞迴版本**"。
## 迭代版本
```cpp=
#include <iostream>
using namespace std;
/// @brief binarySearch
/// @param arr int 陣列，需排好序
/// @param left arr 搜索的起始範圍
/// @param right arr 搜索的終點範圍
/// @param targetNumber 要搜索的目標數字
/// @return returns the index of targetNumber if targetNumber exists in array, otherwise returns -1
int binarySearch(int arr[], int left, int right, int targetNumber)
{
int index = -1;
cout << "binarySearch Start," << "targetNumber:" << targetNumber <<
", search range:" << left << " to " << right<< "\n" <<endl;
while (left <= right)
{
//避免 Overflow，不使用 (left+right)/2 來計算 mid
int mid = left+(right-left)/2;
int midOfArr = arr[mid];
cout << "left:" << left << ", right:" << right
<< ", mid:" << mid << ", arr[mid]:" << midOfArr <<"\n"<<endl;
// 如果找到目標數字，跳出迴圈
if(midOfArr == targetNumber)
{
cout << "Find targetNumber!" << endl;
index = mid;
break;
}
// 若是 mid 比目標數字大，代表 mid 在 目標數字右側，將 right 替換成 mid-1 繼續搜索
// 反之則代表 mid 在 目標數字左側，將 left 替換成 mid+1 繼續搜索
if(midOfArr > targetNumber)
{
cout << "Replace right by " << mid-1 << endl;
right = mid-1;
}
else
{
cout << "Replace left by " << mid+1 << endl;
left = mid+1;
}
}
if(index != -1)
{
cout << "The " << targetNumber <<" is at the index: " << index << " of Array" << endl;
}
else
{
cout << "Can't find " << targetNumber << endl;
}
cout << "\n" << "binarySearch End" << endl;
return index;
}
int main()
{
int arr[] = {1,2,3,5,7,9,11,13,17,19,23};
binarySearch(arr, 0, 10, 7);
}
```
結果:
## 遞迴版本
```cpp=
#include <iostream>
using namespace std;
/// @brief binarySearch
/// @param arr int 陣列，需排好序
/// @param left arr 搜索的起始範圍
/// @param right arr 搜索的終點範圍
/// @param targetNumber 要搜索的目標數字
/// @return index of targetNumber if targetNumber exists in array, otherwise returns -1
int binarySearch(int arr[], int left, int right, int targetNumber)
{
//避免 Overflow，不使用 (left+right)/2 來計算 mid
int mid = left+(right-left)/2;
int midOfArr = arr[mid];
cout << "left:" << left << ", right:" << right
<< ", mid:" << mid << ", arr[mid]:" << midOfArr <<"\n"<<endl;
if(right < left)
{
cout << "Can't find " << targetNumber << endl;
return -1;
}
if(midOfArr == targetNumber)
{
cout << "Find targetNumber!" << endl;
cout << "The " << targetNumber << " is at the index: "
<< mid << " of Array" << endl;
return mid;
}
if(midOfArr > targetNumber)
{
cout << "Replace right by " << mid-1 << endl;
return binarySearch(arr, left, mid-1, targetNumber);
}
else
{
cout << "Replace left by " << mid+1 << endl;
return binarySearch(arr, mid+1, right, targetNumber);
}
}
int main()
{
int arr[] = {1,2,3,5,7,9,11,13,17,19,23};
int sizeOfArr = sizeof(arr)/sizeof(arr[0]);
binarySearch(arr, 0, sizeOfArr-1, 7);
}
```
結果:
# Why Sorted?
簡單考慮下列沒有完全排序的陣列:
```cpp!
int arr[] = {100,1,3,5,7,9,11,13,17,19,23};
```
可以發現今天如果要是搜尋數字 100 的話，<font color='red'>**100 在第一次搜索時就會被排除出搜索範圍了** </font>。
(~~除非 left = right = 0~~ XD)，而 100 卻存在在陣列中，這合理嗎??? 這不合理 :))。
因此我們可以由此例子知道 Binary Search 的搜尋的 Array 必須是排序的。
```cpp!
int sizeOfArr = sizeof(arr)/sizeof(arr[0]);
binarySearch(arr, 0, sizeOfArr-1, 100);
```
(100 明明存在在陣列中，但是卻因為陣列沒有完全排序，所以找不到)
# Bisection Method
Binary Search 的概念其實除了可以用來尋找 Array 內 是否有指定的數字外，也可以很簡單地用來估計連續函數 $f$ 的根喔，這個用來估計的方法被稱為 **"Bisection Method"**。
假設今天有一連續函數 $f:\mathbb{R}\to\mathbb{R}$ 滿足 $f(a)f(b) < 0,\ a < b,$ 則根據中間值定理，必存在 $c\in(a,b)$ 使得 $f(c) = 0.$ 此時我們可以用 Binary Search 的概念對 $c$ 進行估計，估計流程如下:
:::info
:::
現在就讓我們以 $f(x) = x^3 + 1$ 為例，實作 Bisection Method 吧。
```cpp!
#include <iostream>
#include <cmath>
using namespace std;
// f(x) = x^3 + 1
double f(double x)
{
return pow(x,3)+1;
}
/// @brief BisectionMethod
/// @param left number such that f(left) * f(right) > 0
/// @param right number such that f(left) * f(right) > 0
/// @param epsilon error
/// @param f target function
/// @return x with |f(x)| <= error
int bisectionMethod(double left , double right , double epsilon , double (*f)(double x))
{
double f_left = f(left);
double f_right = f(right);
double mid = left+(right-left)/2;
double mid_Of_fun = f(mid);
cout << "left:" << left << ", right:" << right
<< ", mid:" << mid << ", mid_Of_fun:" << f(mid) << endl;
if(mid_Of_fun == 0)
{
cout << "f(mid) = " << 0 << ", where mid = " << mid << endl;
return mid;
}
if(abs(mid_Of_fun) <= epsilon)
{
cout << "|f(mid)| = |" << mid_Of_fun << "| <= " << epsilon <<
", where mid = " << mid << endl;
return mid;
}
if(f_left * mid_Of_fun < 0)
{
cout << "Replace right by " << mid << "\n" << endl;
return bisectionMethod(left, mid, epsilon, f);
}
else
{
cout << "Replace left by " << mid << "\n" << endl;
return bisectionMethod(mid, right, epsilon, f);
}
}
int main()
{
//執行 BisectionMethod，f(x) = x^3+1, f(-2) * f(1) < 0
bisectionMethod(-2, 1 , 0.01, &f);
}
```
執行結果:
# Observation
1.我們可以從流程圖簡單的發現，令 $x_i$ 為 執行第 $i$ 次流程時的中間點 mid，當執行 $n$ 次流程時，$$|x_i -c|\leq\frac{b-a}{2^{i}}, 1\leq i \leq n.$$
因此若是拿掉$|f(mid)|$ 小於誤差的判斷，且流程"**永遠沒有終止**"的話，我們會有 $$\lim_{n\to\infty} x_n = c.
$$
因為 $f$ 是連續的，所以
$$\lim_{n\to\infty} f(x_n) = f(c).$$
白話來說就是 $n$ 則夠大時，$f(x_n)\approx f(c).$
因此只要是在電腦能計算的極限內且 $|f(x_n)|$ 小於誤差，我們就求得我們想要的估計了。
2.若是 $f$ 不是連續的，則 bisection Method 的作法不見得能幫我們估計 $f$ 的根， eg:
$$f(x) =
\begin{cases}
1 & \quad \text{if } x \geq 0. \\
-1 & \quad \text{if } x < 0.
\end{cases}
$$
# Reference
1. https://www.geeksforgeeks.org/binary-search/
2. https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95
3. https://en.wikipedia.org/wiki/Bisection_method
Sign in with Wallet
Connect another wallet