Day26. 實作練習：Binary Search

2024 iThome 鐵人賽

DAY 26

佛心分享-IT 人自學之術

Python學習馬拉松：30天挑戰系列第 26 篇

16th鐵人賽

sheep

2024-10-10 22:24:09

61 瀏覽

分享至

教學來源：https://www.youtube.com/watch?v=8ext9G7xspg
這段程式碼的目的是比較兩種不同的搜尋方法（naive search 和 binary search）的效能，用來尋找目標值在一個排序過的列表中的位置。這裡的重點是「二分搜尋法（binary search）」，它是一種高效的搜尋演算法，特別是在已經排序的列表中。
程式碼與執行結果：

程式碼說明：

naive_search 函數：
◆ 這是最簡單的搜尋方式，叫做「線性搜尋」，它會從列表的第一個元素開始，逐個比對，直到找到目標值或是列表的最後一個元素。
◎ l是排序好的列表。
◎ target 是你想要搜尋的目標值。
◎ 程式會逐一檢查列表中的每個元素，當發現某個元素與目標值相等時，會回傳該元素的索引（位置）。
◎ 如果找不到目標值，會回傳 -1 表示失敗。
binary_search 函數：
◆ 這是二分搜尋法，透過不斷將搜索範圍縮小一半來尋找目標值，比線性搜尋更有效率，但前提是列表必須事先排好順序。
◎ l是排序好的列表。
◎ target 是你想要搜尋的目標值。
◎ low 和 high 定義了當前搜尋的範圍。如果第一次呼叫時沒有給定，會默認範圍是整個列表（從 0 到 len(l)-1）。
◆ 函數會計算目前範圍的中點 midpoint，並根據目標值與中點值的大小關係決定下一步：
◎ 如果中點值等於目標值，回傳中點位置。
◎ 如果目標值小於中點值，繼續在左半邊（從 low 到 midpoint-1）進行搜尋。
◎ 如果目標值大於中點值，則在右半邊（從 midpoint+1 到 high）繼續搜尋。
◆如果 low 大於 high，表示目標值不存在於列表中，回傳 -1。
主程式：
◆ 主程式的主要任務是生成一個隨機的、排序過的列表，然後分別用線性搜尋和二分搜尋來尋找每個目標值，並測量每種搜尋方法的執行時間。
◎ 首先，程式生成一個長度為 1000 的隨機數列表，這些數值的範圍在 -3000 到 3000 之間，然後將這個列表進行排序。
◎ 接著，使用 naive_search 和 binary_search 兩種方法來搜尋列表中的每個數字，並計算每次搜尋所花費的時間。
◎ 最後，輸出每次搜尋的平均時間，來比較哪種方法更快。