[二分查找二分搜尋]

[二分查找 binary search] 是一種基於分治策略的高效搜索演算法。它利用資料的有序性，每輪減少一半搜索範圍，直至找到目標元素或搜索區間為空為止。

Important

❓ 給定一個長度為 n 的陣列 nums ，元素按從小到大的順序排列，陣列不包含重複元素。請查找並返回元素 target 在該陣列中的索引。若陣列不包含該元素，則返回 -1。

先初始化指標 i=0 和 j=n-1，分別指向陣列首元素和尾元素，代表搜索區間 [0, n-1]。中括號表示閉區間，其包含邊界值本身。

接下來，迴圈執行以下兩步：

計算中點索引 $m = \lfloor {(i + j) / 2} \rfloor$ ，其中 $\lfloor : \rfloor$ 表示向下取整操作。
判斷 nums[m] 和 target 的大小關係，分為以下三種情況：
1. 當 nums[m] < target ，說明 target 在區間 [m+1, j] 中，因此執行 i=m+1。
2. 當 nums[m] > target ，說明 target 在區間 [i, m-1] 中，因此執行 j=m-1。
3. 當 nums[m] = target ，說明找到 target ，因此返回索引 m。

若陣列不包含目標元素，搜索區間最終會縮小為空。此時返回 -1。

值得注意的是，由於 i 和 j 都是 int 類型，因此 i+j 可能會超出類型的取值範圍。為了避免大數越界，通常採用公式 $m = \lfloor {i + (j - i) / 2} \rfloor$ 來計算中點。

/* 二分查找（雙閉區間） */
int BinarySearch(int[] nums, int target) {
    // 初始化雙閉區間 [0, n-1] ，即 i, j 分別指向陣列首元素、尾元素
    int i = 0, j = nums.Length - 1;
    // 迴圈，當搜索區間為空時跳出（當 i > j 時為空）
    while (i <= j) {
        int m = i + (j - i) / 2;   // 計算中點索引 m
        if (nums[m] < target)      // 此情況說明 target 在區間 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情況說明 target 在區間 [i, m-1] 中
            j = m - 1;
        else                       // 找到目標元素，返回其索引
            return m;
    }
    // 未找到目標元素，返回 -1
    return -1;
}

優點：時間和空間方面都有較好的性能。

局限性：

僅適用有序資料，若輸入資料無序，為了使用二分查找而專門進行排序，得不償失。
僅適用於陣列（連續儲存空間）。
小資料量下，線性查找性能更佳，在演算法題中，常通過將線性查找替換為哈希查找來降低演算法的時間複雜度。
- 線性查找：以時間換空間
- 哈希查找：以空間換時間

二分查找插入點：二分查找不僅可用於搜索目標元素，還具有許多變種問題，比如搜索目標元素的插入位置。

二分查找邊界：

查找左邊界
查找右邊界

線性搜索適用於小型或頻繁更新的資料；

二分查找適用於大型、排序的資料；

哈希查找適合對查詢效率要求較高且無需範圍查詢的資料；

樹查找適用於需要維護順序和支援範圍查詢的大型動態資料。

參考#

第 10 章搜索 - Hello 算法 (hello-algo.com)

[二分查找 二分搜尋]

參考#

[二分查找二分搜尋]