# Algorithms - Binary Search

###### tags: `Algorithms` `javascript` `Computer science` `Binary Search`

### 9 Ace J <font size=1 color='blue'>(台語，發音night ace j ，翻譯：為啥是binary search)</font>
『演算法(*Algorithms*)』本猩至今30年歲月無意識下每天都會接觸到，但並不在意，直至今日本猩終於願意面對這歷史久遠的方法，然而第一印象最深刻的即是『二分搜尋演算法(*Binary Search*)』(後文皆以*Binary Search*表示)他近期出現在我眼中次數大幅提升，我無意間也注意到他了。接下來就一起來學習什麼是 *Binary Search* 吧！

### J係蝦密 <font size=1 color='blue'>(台語，翻譯：binary search 是什麼？)</font>
*Binary Search* 是一種應用在有序條件的序列中找出目標項目的高效演算法。原理即是將有序序列一分為二選擇有可能包含目標項目的那一半，重複一分為二的動作直到剩下一個項目為止。
Demo:
在序列中找出 3
- 有序序列 {1,3,5,7,9}
- 一分為二 {1,3,5,7,9} 中間數為5; 5>3 所以選擇左邊
- (重複動作)一分為二 {1,3} 1<3 所以選擇右邊
- 剩下一位 {3} 3=3

### 咩銃蝦<font size=1 color='blue'>（台語，翻譯：binary search 幹嘛用？）</font>
來了，這裡應該有人會發現說，為什麼要這麼麻煩？不就從頭開始算就好還比較快，高效？！高效在哪裡，聽你在放....喔喔喔太兇是不是重來重來....維～
話說我就是覺得一個一個數蠻簡單的，為何還要搞個什麼演算法然後還那麼麻煩，但事實上歹誌不像憨猩想的那麼簡單，聽我say來，今天序列如果是5個10個數字以內一個個數是蠻快的，程式找更快for迴圈給他用下去連滑鼠點下run的時間都比找到數目標數字的時間還久。
但是，對但是今天如果是數千數萬個項目組成呢？一個一個去數可能也可以找得到but do you want?你說for迴圈用下去啊，好來了聽本猩用效能全開簡直快熱當的腦部運轉解釋給各位大德。

以下解釋
#### *簡易搜尋法*(一個一個找):

for迴圈去尋找的時候我最多必須走$n$個步驟才能知道是否有我要的項目，例如1~9999，我要找9487時，我是不是要走9487次迴圈。

#### 那*Binary Search*呢？
我們要派出『對數(*log*)』運算符號，為什麼是*log*?

##### 這邊來幫大家回味一下*log*:
這邊有一個數$x$是$10$的$y$次方可以表示成 $x=10^y$
那反之$x$在底數10的情況下對數是$y$可以表示成 $log_{10}x=y$

所以用口語描述*binary search*時就是我要將數列一直一分為二直到找出目標或者證明目標不在，所以底數為2然而最大步驟數就是 $log_{2}n$
那套入1~9999要找9487我們要最多要走$log_{2}9999$次以下一一算給你看
<table>
<tr>
<th>步驟</th>
<th>第一組</th>
<th>第二組</th>
</tr>
<tr>
<td>1</td>
<td>1~4999</td>
<td style="background:Green;color:white">5000~9999</td>
</tr>
<tr>
<td>2</td>
<td>5000~7499</td>
<td style="background:Green;color:white">7500~9999</td>
</tr>
<tr>
<td>3</td>
<td>7500~8749</td>
<td style="background:Green;color:white">8750~9999</td>
</tr>
<tr>
<td>4</td>
<td>8750~9374</td>
<td style="background:Green;color:white">9375~9999</td>
</tr>
<tr>
<td>5</td>
<td style="background:Green;color:white">9375~9686</td>
<td>9687~9999</td>
</tr>
<tr>
<td>6</td>
<td style="background:Green;color:white">9375~9530</td>
<td>9531~9686</td>
</tr>
<tr>
<td>7</td>
<td>9375~9452</td>
<td style="background:Green;color:white">9453~9530</td>
</tr>
<tr>
<td>8</td>
<td style="background:Green;color:white">9453~9491</td>
<td>9492~9530</td>
</tr>
<tr>
<td>9</td>
<td>9453~9471</td>
<td style="background:Green;color:white">9472~9491</td>
</tr>
<tr>
<td>10</td>
<td>9472~9481</td>
<td style="background:Green;color:white">9482~9491</td>
</tr>
<tr>
<td>11 <a style="color:blue">find it !</a></td>
<td>9482~9486</td>
<td style="background:Green">
<a style="color:pink">9487</a>
<a style="color:white">~9491</a>
</td>
</tr>

</table>

$log_{2}9999\approx13$ 以上也只用$11$步就找到了是不是長知識了呢！(我是...)

所以呢 **9487步** vs **11步** 這邊就可以體現出*Binary Search*的效能了吧！是吧是吧？！

### 安抓擁<font size=1 color='blue'>（台語，翻譯：binary search 怎麼用？）</font>
本猩說到這邊，是不是應該要去把*Binary Search*實作出來捏？應該要吧？是吧？嘿對！就是接下來就是我們的coding時間！！
等等等等等!!!
先別猴急，這邊還有一些狀況需要解釋，首先感謝你們願意看到這邊，再來就是我相信大家對於*Binary Search*都有一定的基礎概念了，可是要如何將腦中的想法翻譯給電腦執行呢？
人腦很奇妙只需要模糊的指令，就能自行完成中間的串連(這是所謂的腦補嗎？)
但是電腦不是人腦，他只會執行你下的指令，就好比說你下達一道命令給人跟電腦時：
小猩猩：「把拔，過來！」
本猩就會用百米9秒的速度直衝小猩猩面前然後說：「是，什麼事？」

但是如果本猩是個電腦那小猩猩要該要對我下達：

定義：把拔＝電腦自己
過來方法定義：
    跑步方法(true)
    尋路方法...
    閃避障礙物方法...
    辨識小猩猩方法...
    ...
    ...
    
跑步方法(boolean 跑步):
int i =0;
while (跑步) {
    把拔身體向前傾斜20度
    if(i==0){
        把拔左手向前擺動45度
        把拔右手向後擺動45度
        右腳大腿向上提起90度
    }else{
        把拔右手向前擺動45度
        把拔左手向前擺動45度
        左腳大腿向上提起90度
    }
}
...方法不一一贅述

靠很扯耶...
哈，不過就是這麼有趣，來吧開始囉！
所以這邊就會使用到一個叫做***pseudocode***的小方法。

>***Pseudocode:***
**連接人類語言與程式語言的橋樑**
因為人類語言對於電腦來說是不夠精確的，而程式語言又會需要包含眾多細節像是程式語言本身的要求、處理因為不正確的輸入/使用者操作/系統方面導致錯誤等等的問題。
所以人們發展出混合了人類語言與程式語言稱之為*pseudocode*的東東，利用*pseudocode*描述一個功能的邏輯，方便人類理解並且更容易地轉換成程式語言。

*Binary Search Pseudocode*

我們會**輸入**一個有序序列**Array**以及目標數字**target**，以序列中有多少元素**n**，來設定我們的搜索索引**index**範圍**min**,**max**，然後輸出為序列中的索引值**index**。

1. 令 min=0,max=n-1
<font color="blue" size=1>因為index是由0開始排序所以Array最小值為0最大值為n-1</font>

2. 電腦會需要取得**min**與**max**的平均數(無條件捨去)作為猜測的值所以會有一個整數 **guess**
3. 若 **array**[**guess**] 等於 **target**，則停止，找到目標回傳 **guess**
4. 若 **array**[**guess**]小於 **target**，則令**min** = **guess** + 1
5. 除此之外，若**array**[**guess**]>**target**，令 **max** = **guess** - 1.
6. 回到步驟2直到找到**target**或者確認序列裡沒有**target**為止

#### 實際操作

javascript

var binarySearchTarget = function(array,target){
    var min = 0;
    var max = array.length - 1;
    var guess;
    var times=0;//循環次數
    
    //當min>max的時候可以判斷為此序列沒有target
    while(max>=min){
        times++;//循環一次+1
        guess = Math.floor((max+min)/2);//max+min 平均並無條件捨去
        console.log("guess index = " + guess +",min~max = "+array[min]+"~"+array[max]);
        
        if(array[guess] === target){
        //當猜的數字與target相同時回傳guess(index)
            
            console.log("times = "+times);
            return guess;

        }else if(array[guess] < target){
        //當猜的數字小於target時min = guess+1
        
            min = guess + 1; 
            
        }else {
        //當猜的數字大於target時max = guess-1
        
            max = guess - 1;
            
        }
    }
    return -1;
};

驗證

input 1~9999 Array, target 9487

guess index = 4999,min~max = 1~9999
guess index = 7499,min~max = 5001~9999
guess index = 8749,min~max = 7501~9999
guess index = 9374,min~max = 8751~9999
guess index = 9686,min~max = 9376~9999
guess index = 9530,min~max = 9376~9686
guess index = 9452,min~max = 9376~9530
guess index = 9491,min~max = 9454~9530
guess index = 9471,min~max = 9454~9491
guess index = 9481,min~max = 9473~9491
guess index = 9486,min~max = 9483~9491
times = 11
//11步完成
output 9486

### 終貢己故<font size=1 color='blue'>（台語，翻譯：結論）</font>

以上就是本猩對*Binary Srearch*初略的見解下次分享 ***Tree*** 要怎麼種囉！
感謝諸位大德耐心看完，若有什麼建議或糾正都可以提出唷！
甘溫～
###### 資料來源

https://www.khanacademy.org/
https://stackoverflow.com/
https://developer.mozilla.org/