Binary Search(二元搜尋)

什麼是Binary Search？

一種搜尋的方法，速度會比sequential search快
先排序完，跟中間值做比較，一次可以排除一半的值

假設現在有一個陣列叫做temp，總共有10格，我要找的目標是80

陣列temp

step1. 先將陣列裡的值，由小到大排序

（或者由大到小 兩者都可以）

⚠️ 重點是要排序 ⚠️

陣列temp排序完的結果

step2. 設定left, right, mid

left：初始值是陣列最左邊的index
right：初始值是陣列最右邊的index
mid：(left+right)/2

以下面這張圖為例

left = 0;
right = 9;
mid = (left+right)/2;
//mid = 4

陣列示意圖

step3. 檢查你的目標是在mid左邊還是右邊

if(target<temp[mid]){ //代表目標在mid的左邊
    right = mid-1;
}
else{ //代表目標在mid的右邊
    left = mid+1;
}
mid = (right+left)/2;

目標在左邊

因為目標在mid的左邊
所以可以確定temp[mid]~temp[right]，都不會有我們要找的目標
於是，可以快樂的把right改成mid-1

目標在右邊

因為目標在mid的右邊
所以可以確定temp[left]~temp[mid]，都不會有我們要找的目標
於是，可以快樂的把left改成mid+1

假設目標是30，執行一次後，可得

陣列示意圖

step4. 一直重複step3，直到找到為止 或 left在right的右邊

while(left<=right){ //left要真的在左邊，才會繼續執行
    if(target == temp[mid]){
        break;
    }
    else{
        //做step3的事情
    }
}

陣列示意圖

恭喜你找到了～