前兩天我們把排序簡單介紹過，今天我們要進到搜尋演算法的部分，二分搜在Day 3介紹複雜度時也有短暫出現一下喔 ! 這次一樣是要來把他補齊
對了 DFS 和 BFS 也是搜尋演算法 ! 只是搜尋的對象是節點，和這裡的搜尋對象(排序好的陣列)不大一樣

二分搜(Binary search) 是什麼

二分搜尋法是一種在 已排序 的陣列中，快速找出目標值的搜尋方法。
簡單來說就是每比較一次，就把範圍砍半，而不是像循序搜尋(Linear Search)那樣一個一個找過去

用一個比較貼近生活的例子來講好了

假設今天要在 1~100 內猜一個數字，對方只會告訴你「比較大」或「比較小」
最慢的方法一定是從 1 開始一個個慢慢猜

那有沒有比較有效率的方法呢 ?

答案就是每次都猜中間值，例如先猜 50，如果太大的話，就代表答案在 1~49 之間
再猜這個範圍的中間值 25 ...這樣每猜一次，範圍就除二，很快就能找到答案

二分搜尋法就是把這個邏輯套用在陣列搜尋上

用以下例子來解釋 :

假設 要找 target = 25

先設定 left(最左邊索引) 和 right(最右邊索引)

取中間索引 mid = (left + right) / 2

target > arr[mid] (25>18)，所以可以知道目標值在 mid 的右邊，所以是mid+1

下一輪，mid = (left+right)/2=3，進入if ，arr[mid] == target，找到

把上面的寫成步驟

1. 設定 left(範圍最左邊索引)、right(範圍最右邊索引)
2. 取中間索引 mid = (left + right) / 2
3. 比較 arr[mid] 跟目標值 target :
   • 相等 : 找到了，回傳 mid
   • arr[mid] < target : 目標在右半邊，把 left = mid + 1
   • arr[mid] > target : 目標在左半邊，把 right = mid - 1
4. 重複步驟 2~3，直到 left > right (代表找不到) 或找到目標

程式碼

int binarySearch(int arr[], int n, int target) {

    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (right + left) / 2; 
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 找不到
}

複雜度

平均時間複雜度 : O(log n) ， 每次比較皆排除一半的搜尋範圍
最壞時間複雜度 : O(log n) ，搜尋目標不存在
空間複雜度 : O(1) ， 僅使用 left, right, mid，不需要額外配置空間

那接下來，我們明天會繼續來看插補搜尋法，了解比二分搜尋法更進階的搜尋法