# 二分搜尋法（Binaray Search)

## 為何要二分搜尋
假設今天有一個由小到大的陣列，但沒有一定的規律性
{1,3,7,8,11,14......,763,5252}
那我想找到 763 這個數字，初學者都會利用

`for(int i = 0; i < sizeof(array)/sizeof(array[0]); i++) `

去找尋
但這會遇到一個問題，如果今天array的大小為10萬
然後又剛好數字是最後一個，不就要跑10萬次
那100萬的情況，大概就是吃TLE

這時就得用上二分搜尋去縮短時間

## 什麼是二分搜尋 📖cccc

用最大值跟最小值去做判斷不停的壓縮這兩個範圍，直到找到答案
玩過猜數字遊戲吧？
沒玩過也沒關係，稍微解釋這遊戲
今天預設答案為 70 範圍為 1 ~ 100，請你去做猜測
這時
猜：90，官方：比較小，這時你知道範圍縮小為 1 ~ 90
猜：65，官方：比較大，這時你知道範圍縮小為 65 ~ 90
二分搜尋就類似這種做法

## 示範Code

#include <stdio.h>
#define ma 12
void BinarySearch(int array[], int goal)
{
    int left = 0, right = ma - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == goal)
        {
            printf("Find the goal : %d\n", mid);
            break;
        }
        else if (array[mid] > goal)
        {
            right = mid - 1;
        }
        else if (array[mid] < goal)
        {
            left = mid + 1;
        }
    }
    if (left > right)
    {
        printf("No find the answer\n");
    }
}
int main()
{
    int array[ma] = {1, 3, 5, 6, 7, 8, 9, 11, 15, 19, 21};
    BinarySearch(array, 19);
    BinarySearch(array, 10);
    return 0;
}

## 幾個問題❓

### 1. 為何要 right = ma - 1
因為陣列大小開12，但電腦是從 0 開始的
所以實際上數字是存放在 0,1,2,3,...,9,10,11

### 2. 為何要 while(left <= right) 而非 while(left < right)
因為當答案剛好在 left == right 時，才不會遺漏掉

### 3. 為何在判斷時，left = mid + 1, right = mid - 1
因為 mid 的位置我們就可以不用在看了

舉例：
當 array[mid] < goal 時
就代表 mid 之前的數字都不用看(包括mid)
因此left = mid + 1

當 array[mid] > goal 時
就代表 mid 之後的數字都不用看(包括mid)
因此left = mid - 1

## 上課練習
[LeetCode](https://leetcode.com/problems/search-insert-position/)
## 參考
[二分搜](https://hackmd.io/@SupportCoding/Binary_search)
[二分搜-2](https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1)