# 二分搜尋法(binary search)
配合圖片二分搜會學的比較輕鬆，在進行二分搜前可以先畫一個$1$ * $n$的矩陣來幫助理解
以上為一個$1$*$9$的矩陣，每個格子中儲存一個數字，切記在進行二分搜得時候要先把數字排好，我習慣由小排到大，而接下來就可以進行搜尋了。
假設我們要搜尋的目標是<span style = "color:red">`14`</span>我們先將矩陣的數量除二，可得目前index值為(0+8)/2 = 4，而index[4]的位置並非我們要找的數值，且index[4] = 9小於我們的目標14所以我們直接拋棄尋找小於9的數字，直接往以9為中心的右側繼續尋找下一個，一直重複此動作即可尋找到`14`的位置。

我們之所以要使用binary search 而不用linear search是因為linear search的time complexity 是O(n) 而binary search 的 time complexity 是O(logn)比較快。

程式碼:

#include <iostream>
#include <algorithm>
using namespace std;
int Binary_search(int * arr,const int target,int left,int right);
int main(){
    int arr[10] = {3,19,23,8,14,6,9,1,20};//1,3,6,8,9,14,19,20,23
    const int target = 14;
    sort(arr,arr+9);
    int position = Binary_search(arr,target,0,8);
    cout << position+1 << endl;

    return 0;
}
int Binary_search(int * arr,const int target,int left,int right){
    while(left < right){
        int mid = (left+right)/2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] > target) right = mid;
        else if(arr[mid] < target) left = mid+1;
    }
}