作為大多數人一開始學程式就學到的搜尋演算法，不過多引入介紹，這邊主要提一些基本概念

線性搜尋法 Linear Search

又稱循序搜尋法，這是最直觀的方法(把所有東西都過一遍)，這樣就可以找到想要的內容了
線性搜尋法很簡單，對於一個陣列，只需要每個依序比較是否相同即可

    int arr[10] = {1,3,5,7,11,13,17,19,23,29};

    int target_number = 13;
    for(int i = 0 ; i < 10 ; i++){
		if(arr[i] == target_number){
			cout << "Found the number";
		}
    }

時間複雜度: O(n)
問題:太慢了

二分搜尋法 Binary Search

可以理解成把一串序列不斷地從中間分成兩堆、檢查、分成兩堆...，我們定義兩個索引代表邊界(左/右邊界)
這邊重點講一下常常會有人寫錯的地方: 如何定義索引值，常常看到的兩種寫法: 左閉右開跟左閉右閉，兩者對於索引的定義影響了如何更新索引

閉跟開也就是數學常說的閉區間跟開區間，舉例來說：
開區間:(2,3)也就是 2 < x < 3，
而閉區間[2,3]也就是 2 <= x <= 3

舉例來說一個陣列中有 1 2 3 4 5 6總共6個數字，我要表示整個陣列的話，索引範圍如下

• 閉: [0,5]
• 開: [0,6)

這邊先以本人所習慣的寫法左閉右閉為例子，

1. 左閉右閉 [left, right]

在「左閉右閉」的定義下，我們的搜尋範圍包含 left 指向的元素，也包含 right 指向的元素。意即：我們在 [left, right] 這個區間內尋找目標。

核心邏輯

1. 初始化：left = 0, right = n - 1。
2. 迴圈條件：while (left <= right)。
   • 因為是閉區間，當 left == right 時，區間內還有一個元素，仍需檢查。
3. 更新方式：
   • 如果 arr[mid] > target：代表目標在左邊，區間縮小為 [left, mid - 1]，所以 right = mid - 1。
   • 如果 arr[mid] < target：代表目標在右邊，區間縮小為 [mid + 1, right]，所以 left = mid + 1。
   • 如果 arr[mid] == target：找到了！

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

int arr[10] = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n = 10;
int target = 13;

int left = 0;
int right = n - 1; // 定義在 [left, right] 區間搜尋
int ans = -1;      // 儲存結果的索引值

while (left <= right) {
    // 避免 (left + right) 直接相加導致 int 溢位
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        ans = mid;
        break; // 找到目標，跳出迴圈
    } else if (arr[mid] < target) {
        left = mid + 1; // 目標在右半部 [mid + 1, right]
    } else {
        right = mid - 1; // 目標在左半部 [left, mid - 1]
    }
}

if (ans != -1) cout << "Found at index: " << ans;
else cout << "Not found";

2. 左閉右開 [left, right)

在「左閉右開」的定義下，搜尋範圍包含 left 指向的元素，但不包含 right 指向的元素。
這意味著：我們在區間 [left, right) 內尋找，當 left == right 時，代表區間內已經沒有任何元素，搜尋結束。

核心邏輯：

1. 初始化：left = 0, right = n（注意：right 是指向最後一個元素的下一個位置）。
2. 迴圈條件：while (left < right)。
   • 因為是右開，當 left == right 時區間已空，所以不需包含 =。
3. 更新方式：
   • 如果 arr[mid] > target：目標在左邊。因為右邊是開區間，我們將 right 更新為 mid，表示下一次搜尋範圍是 [left, mid)（不含 mid）。
   • 如果 arr[mid] < target：目標在右邊。區間縮小為 [mid + 1, right)，所以 left = mid + 1。
   • 如果 arr[mid] == target：找到了！

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

int arr[10] = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n = 10;
int target = 13;

int left = 0;
int right = n; // 指向陣列結尾的下一個位置 (索引 10)
int ans = -1;

while (left < right) { // 當 left == right 時，區間 [left, right) 為空
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        ans = mid;
        break;
    } else if (arr[mid] < target) {
        left = mid + 1; // 範圍變為 [mid + 1, right)
    } else {
        right = mid;     // 範圍變為 [left, mid)，剛好排除掉 mid
    }
}

if (ans != -1) cout << "Found at index: " << ans;
else cout << "Not found";

對照

兩種寫法的快速對照表

3. 二分搜尋法的限制？

這裡只討論 搜尋陣列中的元素

• 前提條件：陣列必須是已排序 (Sorted) 的。
• 時間複雜度： O(log⁡n)
  每次比較都能排除掉一半的資料。
• 舉例：
• 若有1,000,000筆資料，線性搜尋最差要找 1,000,000次，二分搜尋只需要約 log⁡2(1,000,000)≈20 次。

這系列主要是我個人的學習歷程(不代表每個演算法的難度)，作為剛學程式不久的人來寫寫筆記紀錄，對剛開始學程式的人來說，可以讓你對大部分基本演算法有個基礎概念，可能不是那麼的詳盡，但我想應該還是有幫助，如果內容有偏誤也歡迎指正，希望對你有幫助!