掌握二分查找演算法：初始化、查找區間與終止條件

二分查找演算法應用於有序序列，其核心思想是通過比較中間元素和目標元素，每次縮小一半的查找區間，從而實現快速搜索。具體步驟如下：

1. 定義查找區間
2. 取查找區間中間元素，與目標元素進行比較
   1. 若相同，則返回
   2. 若不同，縮小查找區間，直到區間中沒有待查找元素

在實現二分查找演算法時，需特別注意以下細節：left、right 變數的初始化、終止條件以及查找區間的縮小。要確保查找過程中不漏掉任何元素，並保持前後區間性質的一致性。什麼是保證區間性質的一致性呢？就是說你一開始定義的初始化的區間是閉區間，後面縮小的過程中就不能突然縮成半開半閉區間。

left，right變數對應當前查找區間的範圍。

查找某個元素

以升序序列 vector nums 為例，假設我們按以下方式初始化 left 和 right：

int left = 0, right = nums.size() - 1;

這意味著初始查找區間為閉區間 [left, right]。後續代碼應基於此編寫，例如：

while (left <= right)
{
    int middle = left + (right - left) / 2; // 防止溢出
    if (nums[middle] == target)
    {
        return middle;
    }
    else if (nums[middle] > target)
    {
        left = middle + 1;
    }
    else if (nums[middle] < target)
    {
        right = middle - 1;
    }
}
return -1;

首先分析終止條件。在這裡，由於是閉區間，left <= right 的條件對應的終止情況是 left == right + 1，此時查找區間為 [right + 1, right]，即空區間，說明所有元素都被查找完了。否則，如果是left target 的情況中：

{
    int middle = left + (right - left) / 2;
    if (nums[middle] >= target)
    {
        right = middle - 1;
    }
    else if (nums[middle] < target)
    {
        left = middle + 1;
    }
}

最後考慮應該返回left還是right。結束時，根據終止條件和縮小區間的代碼，可知此時應該滿足left = right + 1、nums[right + 1] >= target、nums[left - 1] = target、nums[right] = target 和 nums[left - 1] = target 和 nums[right] < target。因此，這裡應返回 left。

其他情況同理。

本文鏈接: https://linuxstory.org/mastering-binary-search-initialization-interval-termination

LinuxStory 原創教程，轉載請註明出處，否則必究相關責任。