教程長篇分享

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

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

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

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

leftright變數對應當前查找區間的範圍。

查找某個元素

以升序序列 vector nums 為例,假設我們按以下方式初始化 leftright

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 + 1nums[right + 1] >= targetnums[left - 1] = targetnums[right] = targetnums[left - 1] = targetnums[right] < target。因此,這裡應返回 left

其他情況同理。


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

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

對這篇文章感覺如何?

太棒了
0
不錯
0
愛死了
0
不太好
0
感覺很糟
0

You may also like

Leave a reply

您的電子郵箱地址不會被公開。 必填項已用 * 標註

此站點使用Akismet來減少垃圾評論。了解我們如何處理您的評論數據

More in:教程

教程

PuTTY 使用綜合指南:SSH 連接 Linux

無論您是經驗豐富的開發人員還是初學者,想在您的計算機和遠程 Linux 伺服器之間建立安全連接,PuTTY 是一個值得信賴的工具。讓我們深入了解如何在 Windows 操作系統上利用 PuTTY 進行 […]