Algo python 作者: Joy Liu

【Python】Binary Search 二分搜尋｜演算法介紹、新手快速入門

基本概念

二分搜尋（Binary Search）是一種高效的搜尋演算法，用於在已排序的數列（通常是陣列或串列）中尋找特定元素的位置或值。其基本概念如下：

前提條件：

  • 資料集合必須是已排序的，可以是升序或降序排列。這是因為二分搜尋利用了排序順序來有效地縮小搜索範圍。

步驟：

  1. 初始化左右邊界：將搜尋範圍的左邊界 left 設為 0，右邊界 right 設為資料集合的最後一個元素的索引。
  2. 重複以下步驟，直到左邊界 left 大於右邊界 right：
    • 計算中間索引 mid，可以使用 mid = (left + right) // 2。
    • 檢查中間元素 arr[mid] 與目標元素 target 的比較：
      • 如果 arr[mid] 等於 target，則找到目標元素，返回 mid。
      • 如果 arr[mid] 大於 target，則將右邊界 right 設為 mid - 1，縮小搜索範圍為左半部分。
      • 如果 arr[mid] 小於 target，則將左邊界 left 設為 mid + 1，縮小搜索範圍為右半部分。
  3. 如果搜索範圍內找不到目標元素，則返回 -1，表示目標元素不存在於數列中。

特點：

  • 二分搜尋是一種高效的搜尋演算法，因為它可以在每次迭代中將搜索範圍縮小一半，而不是線性搜索逐一檢查每個元素。
  • 時間複雜度為 O(log n)，其中 n 是資料集合中的元素數量。因此，二分搜尋適用於大型排序數列。
  • 二分搜尋通常用於數列搜尋，但也可以應用於其他已排序的數據結構，如二叉搜尋樹。

二分搜尋是一個高效的搜尋演算法，特別適用於已排序的數列中尋找目標元素。它的主要優勢在於其快速的搜索速度，特別在大型資料集合中表現出色。

實際應用

以下是使用 Python 實際運用二分搜尋的範例。假設我們有一個已排序的數列（陣列），我們想要找到特定的數字是否存在於數列中，以及它的索引位置（如果存在）。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # 初始化左右邊界

    while left <= right:
        mid = (left + right) // 2  # 計算中間索引

        if arr[mid] == target:
            return mid  # 找到目標元素，返回索引位置
        elif arr[mid] < target:
            left = mid + 1  # 縮小搜索範圍為右半部分
        else:
            right = mid - 1  # 縮小搜索範圍為左半部分

    return -1  # 目標元素不存在於數列中，返回-1

# 測試
my_list = [2, 4, 7, 12, 15, 21, 30, 34, 42]
target_number = 15

result = binary_search(my_list, target_number)

if result != -1:
    print(f"目標數字 {target_number} 存在於數列中，索引位置為 {result}")
else:
    print(f"目標數字 {target_number} 不存在於數列中")

在這個範例中，我們定義了一個名為 binary_search 的函數，它接受兩個參數：一個已排序的數列 arr 和一個目標數字 target。函數使用二分搜尋的算法來尋找目標數字。我們初始化左邊界 left 為 0，右邊界 right 為數列的最後一個元素的索引，然後在每次迭代中根據中間元素的值與目標值的比較，縮小搜索範圍。

在測試部分，我們創建了一個已排序的數列 my_list 和一個目標數字 target_number，然後調用 binary_search 函數來尋找目標數字。最後，我們根據返回值判斷目標數字是否存在於數列中，並打印相應的訊息。

使用案例

二分搜尋（Binary Search）是一種高效的搜尋算法，特別適用於已排序的數據集。以下是一些二分搜尋程式案例應用：

  1. 查找元素： 最常見的用途是在已排序的數列或列表中查找特定的元素。因為數據已經排序，所以你可以迅速縮小搜索範圍，從而實現快速查找。
  2. 字典或詞彙搜尋： 在字典或詞彙中查找單詞或詞彙時，可以使用二分搜尋，特別是當詞彙是按字母順序排列時。
  3. 庫存管理系統： 在庫存管理系統中，你可以使用二分搜尋來查找特定產品或物品的庫存信息。庫存項目通常按照產品編號或名稱排序。
  4. 數學方程求解： 在數學應用中，你可以使用二分搜尋來解方程或找到方程的根。通過不斷縮小可能的解的範圍，可以高效地找到解。
  5. 遊戲開發： 在遊戲中，你可以使用二分搜尋來實現各種功能，如查找玩家在排行榜中的位置、確定物體是否在特定範圍內等。
  6. 日曆應用： 在日曆應用中，你可以使用二分搜尋來查找特定日期，尤其是當日期已按日期順序排列時。
  7. 簡單排序： 雖然二分搜尋主要是一個查找算法，但也可以在排序中使用。你可以使用二分搜尋來找到應該插入的位置，以實現插入排序。
  8. 音樂播放器： 在音樂播放器中，你可以使用二分搜尋來查找特定歌曲或歌手，特別是當音樂庫已按標題或藝術家名稱排序時。
  9. 路線規劃： 在地圖或路線規劃應用中，你可以使用二分搜尋來查找最接近的地點或路徑，以提高搜索速度。

其他演算法快速通道：

  1. 【Python】什麼是演算法？
  2. 【Python】Stack(堆疊) 資料結構實作
  3. 【Python】linear search 線性搜尋
  4. 【Python】binary search 二分搜尋
  5. 【Python】Single Linked List(單向鏈結串列) 資料結構實作
  6. 【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(1)
  7. 【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(2)

線上學習平台推薦

udemy

我自己最愛用的學習平台是 udemy ，當初會選擇在 udemy 上學習的原因除了課程便宜（當初買的很多課程都300塊左右，是台幣喔台幣！）。

上課時間也可以自己控制（對自律的人來說是一大好處！）

雖然可能有些人會覺得，Youtube上不也很多Tutorials嗎？性質應該差不多吧？而且免費。

雖然看Youtube上也有教學影片，但其實你會發現，這些老師都有另外開課程。

原因也很簡單，只要我們付費購買了他的課程，他就能提供更多的資源來輔助學習，且更有組織的教學過程，甚至有被公司認可的證書。

這就是在免費的youtube上沒辦法做到的。

想知道更多的話，歡迎到【2023】10個使用線上平台學習的好處｜學生、工程師、各行各業皆適用 看完整介紹。

點擊加入Udemy

推薦入門書籍

精通 Python：運用簡單的套件進行現代運算（第二版）

博客來-精通Python：運用簡單的套件進行現代運算（第二版）

之前開始入坑python時就是用這本打底的（有換封面過）

這本書除了前幾張介紹基本的語法之外

後續幾張開始介紹與python相關的延伸性的功能

非常適合程式設計初學者以及剛要開始學習這個語言的讀者

羅列以下幾點關於本書大綱供大家參考

  • 學習簡單的資料類型、基本數學運算與文字操作 
  • 以Python的內建資料結構處理資料 
  • 探索Python程式碼結構，包括函式的使用
  • 使用模組與套件編寫大型Python程式
  • 深入討論物件、類別與其他物件導向功能
  • 檢視一般檔案、關聯式資料庫與NoSQL的儲存機制 
  • 使用Python建構web用戶端、伺服器、API與服務 
  • 管理系統工作，例如程式、程序與執行緒
  • 瞭解並行處理與網路程式設計的基礎
前往博客來購買 -- 中文版
前往博客來購買 -- 英文版

流暢的 Python：清晰、簡潔、有效的程式設計

博客來-流暢的Python：清晰、簡潔、有效的程式設計

適合已經有Python程式語言基礎的人

這本書更詳細的介紹有關python的用法

讓我們寫的程式可以更加"Pythonic"

建議可以與英文版同時閱讀

以後在查閱stackoverflow文獻的時候能不因語言而產生隔閡

  • Python 資料模型：瞭解特殊方法是讓物件具備一致行為的關鍵
  • 資料結構：充分使用內建的型態，並瞭解 Unicode 時代中，文字 vs. bytes 之間的關係
  • 函式就是物件：見識 Python 函式是一級物件，並瞭解這個事實如何影響熱門的設計模式
  • 物件導向的習慣用法：學習參考、可變性、介面、運算子多載與多重繼承，並建構類別
  • 控制流程：藉由 concurrent.futures 與 asyncio 套件，來充分活用情境管理器、產生器、協同程序與並行
  • 中繼編程：瞭解特性、屬性描述器、類別修飾器與中繼類別的工作原理
前往博客來購買 -- 中文版
前往博客來購買 -- 英文版

演算法圖鑑

直觀理解，從基礎開始學習，全圖像化step by step，讓不懂程式的人也能利用圖形了解各種演算法的特質跟運作．

雖然內容並沒有程式實作

但內容演算法流程圖片非常精美

非常適合用來教學或以圖像的方式了解演算法的運作！

前往博客來購買 — 中文版

Python 自動化的樂趣：搞定重複瑣碎&單調無聊的工作(第二版)

Python 自動化的樂趣｜搞定重複瑣碎& 單調無聊的工作(中文版) (Automate the Boring Stuff with Python: Practical Programming for Total Beginners) | 天瓏網路書店

如果想使用自動化來增強工作流程效率，大推本書

之前這本書只有英文版

在博客來等了1個月還是沒等到

沒想到在2020/08/28 出了中文版

二話不說馬上看看人家都是怎麼用python來完成例行公事的

除了運用Python寫出程式，在幾分鐘內搞定人工手動處理需要花費數小時的工作。

探索Python豐富的模組程式庫來完成某些特定工作

例如從網站上抓取資料、讀取PDF和Word文件，以及自動化執行滑鼠點按和鍵盤輸入的工作。

　‧在一個或多個檔案中搜尋文字
　　‧建立、更新、搬移和重新命名檔案和資料夾
　　‧搜尋網頁和下載網路上的圖文內容
　　‧處理PDF檔的分割與合併，加入浮水印和加上密碼等作業
　　‧傳送Email和簡訊
　　‧填寫線上表單

前往博客來購買 — 中文版
前往博客來購買 — 英文版

在〈【Python】Binary Search 二分搜尋｜演算法介紹、新手快速入門〉中有 4 則留言

  1. 自動引用通知: 【Python】linear search 線性搜尋｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式
  2. 自動引用通知: 【Python】Bubble Sort 泡沫排序｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式
  3. 自動引用通知: 【Python】Insertion Sort 插入排序｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式
  4. 自動引用通知: 【Python】Selection Sort 選擇排序｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *