前置知識：
【演算法新手村】[初階]筆記01 - 初識二分之二分搜尋
配合使用效果更佳喔XD

二分搜尋的題目有不少，這邊講一些簡單的(難的跳過，請新手上路者放心食用)

二分搜尋有一個進階延伸二分搜尋答案也就是二分答案，由於難度較高這邊先跳過

基礎類型

在尋找某一個特定值 target 上可以分成三種：

• 確定 target  是否存在
• 找到第一個大於等於 target  的位置 ( >= target 之最左)
• 找到最後一個小於等於 target  的位置( <= target 之最右)

確定 target  是否存在

直接用上一章中講到的就可以，C的返回值可以用int，C++用bool更好

程式碼實作 (C)

int binary_search_exists(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1; // 左閉右閉 [left, right]
    int ans = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            ans = mid;
            break;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    if(ans == -1)
        return 0; // 沒找到
    else
        return 1; // 找到了
}

或者你要找到直接返回，沒在迴圈中返回表示沒找到

int binary_search_exists(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1; 

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

在主函式呼叫他

int main() {
    int arr[10] = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int target = 13;
    int res = binary_search_exists(arr, 10, target);
    if (res == 1) {
        printf("Found!\n");
    } else {
        printf("Not Found!\n");
    }
    return 0;
}

程式碼實作 (C++)

可以從C的兩種直接改過來，替換成bool即可，為了避免冗長且相似過高，這邊只貼一種

bool binary_search_exists(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1; 

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return true;  // 找到了直接回傳 true
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false; // 迴圈跑完都沒找到，回傳 false
}

主函式也是跟C幾乎相同，資料類型改一下就好

int main() {
    int arr[10] = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int target = 13;
    bool res = binary_search_exists(arr, 10, target);
    if (res) {
        printf("Found!\n");
    } else {
        printf("Not Found!\n");
    }
    return 0;
}

找 >= target 之最左位置

這個問題的核心在於：
當我們發現 arr[mid] >= target 時，雖然 mid 可能就是答案，但其左邊可能還有其他也滿足 >= target 的元素。因此，我們需要用一個變數 ans 記錄目前找到的候選位置，並繼續往左半邊搜尋，文字上可能有些模糊，舉例說明如下
假設目前狀態如圖所示，我們要找 >= target 之最左位置

先正常進行二分，找到符合 >= target時記錄下位置，更新 ans (ans = mid)

因為如果 arr[mid] >= target符合時，代表右手邊的都符合條件(皆 >= target，這是一個有排序過的陣列)，當前位置mid是已知條件中符合且最靠左邊的(右手邊雖都符合條件，但不是最左邊；左手邊可能比target大也可能小我們不清楚，但是由於左邊的位置比mid好，所以必須進行檢查)，此時我們只要去看左手邊有沒有同樣符合條件的，所以往左邊搜尋

之後依序更新 right 跟 mid

注意當前的arr[mid]沒有>= target，所以不要更新ans

同理，因為如果 arr[mid] >= target不符合時，代表左手邊的都不符合條件，當前位置mid是不符合條件的，右邊的部分比arr[mid]大(可能比target大也可能小我們不清楚，所以進行搜尋)，所以往右邊進行搜尋。

更新 left 跟 mid

此時arr[mid]符合>= target，記錄下位置，更新 ans (ans = mid)

更新後，left <= right不成立，退出迴圈

程式碼實作 (C/C++)

int find_first_greater(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    int ans = -1; // 初始化為 -1，代表找不到滿足條件的數

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] >= target) {
            ans = mid;       // 記錄目前找到的位置
            right = mid - 1; // 嘗試去左邊找更左的位置
        } else {
            left = mid + 1;  // 太小了，往右邊找
        }
    }
    return ans;
}

為什麼不能直接 return？

在「確定是否存在」的邏輯中，我們看到 arr[mid] == target 就收工了。但在「找最左位置」時，如果target 是 13 而陣列是{1, 13, 13, 13, 20} ：
第一輪 mid 指到第二個的 13。 (如果直接返回就錯了)
不能停下，紀錄下這個 mid，然後把搜尋範圍縮小到 mid 的左邊，看看還有沒有更早出現的 13（或滿足條件的數）。
如果左邊沒了，最後記錄的那個 ans 就會是最左邊的位置。

補充：找 > target 之最左位置 (Upper Bound)

如果你要找的是「第一個嚴格大於 target」的位置，邏輯幾乎一模一樣，只需要改動一個符號：
if (arr[mid] >= target) (找第一個大於等於)
if (arr[mid] > target) (找第一個嚴格大於)

找 <= target 之最右位置

跟剛剛的東西概念差不多，只是大小關係跟搜尋方向不同而已。

程式碼實作 (C/C++)

int find_last_le(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    int ans = -1; // 若陣列中所有數都 > target，則回傳 -1

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] <= target) {
            ans = mid;      // 記錄目前滿足條件的位置
            left = mid + 1; // 嘗試去右邊找更右（更大索引）的位置
        } else {
            right = mid - 1; // 太大了，往左邊縮小範圍
        }
    }
    return ans;
}

總結

在手寫二分搜尋時，只要掌握「保留可能答案」的原則：
找最左位置 (>= target)：
滿足條件 arr[mid] >= target 時，ans = mid，然後 right = mid - 1 (往左找)。
找最右位置 (<= target)：
滿足條件 arr[mid] <= target 時，*ans = mid，然後 left = mid + 1 (往右找)。

注意事項

C有bool用嗎?

C語言的stdbool.h 是在 C99 標準中正式加入的，之後的版本都可以加上

#include <stdbool.h> 

來引入標頭檔(header file)作為使用
由於很多讀者應該是學生，你的學校可能還在用很古老的版本，所以我是用int作為示範，如果你確定你的標準是在C99之後的也可以使用 bool，寫法上就可以照著C++的寫

• true：為 1。
• false：為 0。

怎麼知道陣列的長度?

有時候我們無法提前得知陣列的大小，這個時候就需要我們手動計算陣列大小，我們可以在主函式中計算

程式碼實作 (C/C++)

    int main() {
    int arr[] = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int n = sizeof(arr) / sizeof(arr[0]); // 計算陣列長度
    int target = 13;

    int res = binary_search_exists(arr, n, target);
//  bool res = binary_search_exists(arr, n, target);
    ... //其他相同
}

一定要在主函式中計算!!!

一定要在主函式中計算!!!

一定要在主函式中計算!!!

(很重要所以說三次
嚴謹上來說是在你把陣列交給其他函數前計算，丟給其他函式後其會退化成指標導致丟失長度，所以在副函式中計算出來的會是錯的(不是長度)，這個會在另外筆記說明。

這篇其實很猶豫要不要寫入二分答案的，想了想放在下一篇，下一篇中會有一些習題跟簡單提一下二分答案，現在看起來上一篇有點過於簡略了，明天回去修一下~
希望今天的東西有幫到你，每天都進步一些

-> 【演算法新手村】[初階]筆記03 - 二分練習題