二元搜尋是什麼？

二元搜尋（ Binary Search）是一種用來快速搜尋某元素的演算法。

一般來說，我們在陣列中查找特定元素時，常見的寫法會像這樣

int[] arr = {3, 8, 12, 20, 25, 30, 35};
int target = 25;
int index = -1;

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
        index = i;  //找到了
        break;
    }
}
System.out.println(index);

從陣列的開頭找到結尾，確保沒有漏掉任何一個元素，直到找到我們要找的東西。這種寫法叫做線性查詢（Linear Search），特點是

• 簡單
• 搜尋效率隨資料增大變差

因為最壞情況下必須把整份資料看完（目標不存在於資料內、或是在資料最尾端）。

在 Java 中，例如 ArrayList 的 contains()、indexOf()、lastIndexOf() 等方法，本質上都是線性搜尋的例子。

當資料量變大，線性搜尋的效率會逐漸變差，此時可以使用二元搜尋來處理。

二元搜尋的核心思想

二元搜尋的核心思想是，透過比較資料的方式，每次搜尋時將搜尋範圍減半，直到找到想找的資料。

因為需要比較，所以要使用二元搜尋有個前提：資料必須已排序。

假設資料是 1 ~ 20 ，我們要找的數字是 18，在程式開始找答案前，我們的搜尋區間是 1 ~ 20

每次搜尋要把搜尋區間減半，所以要找出中間值，1 ~ 20 的中間值是 10

每次找出中間值後，我們要判斷這次猜的數字(也就是中間值) 是等於 大於 還是小於我們要找的數字

1. 是等於 ⇒ 直接公布答案
2. 是大於 ⇒ 中間值大於要找的數字，代表數字在左邊（1 ~ 9），那麼右邊就不看了
3. 是小於 ⇒ 中間值小於要找的數字，數字在右邊（11 ~ 20），那麼左邊就不看了

我們要找的數字是 18 ，那麼要把範圍減半，我們捨棄左邊（數字在右邊，左邊就不用看）

就這樣持續的猜，直到猜到我們要找的數字。

常見卡點

以上說明的概念，短短的看起來好像很簡單，但實作起來可能不會那麼順利

在展示實際範例前，大概說明幾個實作二元搜尋過程中，比較值得注意的卡點：

1. 左右邊界定義不清
2. 中間值的計算方式
3. 更新邊界的方法

---

左右邊界定義不清？

假設要從這個陣列找資料：[1,3,5]

index: 0 1 2

value: 1 3 5

左邊跟右邊分別是 1 , 5，此時我們想著”左邊跟右邊都要檢查到” (你可能看過 閉區間[left, right])

但是當你在寫程式的時候這樣寫

while(left < right)

此時你寫的程式跟你心裡想的左右區間定義已經對不上了，拿上面的陣列當例子：

我們要找 5，搜尋過程會是

left = 0
right = 2
mid = 1
nums[mid] = 3

因為 3 < 5

left = mid + 1 = 2 

mid 的 index 是 1，nums[mid] = 3。

因為要排除 mid 本身，所以新的 left 會變成 mid + 1，也就是 index 2。

left = 2
right = 2

當left = right，while left < right 已經 不成立，迴圈直接結束，但你的答案還沒找到。

這就是左右邊界定義不清，你心裡想的查詢方法跟實際寫的方式要對得上，我這樣說其實代表了解法不只這一種，不過在這篇文章我先只說明”左邊跟右邊都要檢查到” 的解法。

---

中間值的計算

中間值的計算方式直覺上這簡單，就是

mid = (left + right) / 2   

但如果你使用的語言是像 java , C++ 那就會有整數溢位的問題，以 java 為例，在 java 中，int (數字) 的範圍是

• 最小值：-2,147,483,648
• 最大值： 2,147,483,647

如果運算結果超過這個範圍，就會發生整數溢位，得到錯誤的數值

例如：

int left  = 2_000_000_000;
int right = 2_100_000_000;
//此時 left + right = 4,100,000,000
//但 Java int 最大值只有 2,147,483,647

要避免這情況，mid 可以這樣算：

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

---

更新邊界

二元搜尋的核心邏輯是

每一次比較nums[mid] 和target，都要把「不可能包含答案的一半區間」丟掉。

當答案只可能在 mid 的右邊，因為左邊的值全部都更小，因此可以把左半部排除。

left = mid + 1    // 移動到 mid 的右邊

反之如果要把右邊丟掉：

right = mid - 1

因為每次搜尋都會更新區間邊界，因此通常會用 while 迴圈來實作二元搜尋。

解題範例

Binary Search（LeetCode 704）

題目給定一個已排序陣列 nums，以及目標值 target，需要找出目標值的索引。如果不存在則回傳 -1。因為陣列已排序，可以用二元搜尋來解。

Java 範例程式：

class Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {

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

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

1. 取得目前搜尋區間的中間位置 mid
2. 如果 nums[mid] 等於 target，直接回傳
3. 如果 nums[mid] 小於 target，代表答案在右半部，更新 left = mid + 1
4. 如果 nums[mid] 大於 target，代表答案在左半部，更新 right = mid - 1

每一次迭代都會把搜尋區間縮小一半，因此時間複雜度是 O(log n)。

在這個實作中，我們使用的是「閉區間 [left, right]」的寫法，迴圈條件是 left <= right，更新邊界時會使用 mid + 1 或 mid - 1 來確保搜尋區間持續縮小。