技術問答
技術文章
iT 徵才
Tag
聊天室
2025 鐵人賽
登入/註冊
問答
文章
Tag
邦友
鐵人賽
搜尋
2024 iThome 鐵人賽
DAY
26
0
佛心分享-IT 人自學之術
Python學習馬拉松:30天挑戰
系列 第
26
篇
Day26. 實作練習:Binary Search
16th鐵人賽
sheep
2024-10-10 22:24:09
224 瀏覽
分享至
教學來源: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 兩種方法來搜尋列表中的每個數字,並計算每次搜尋所花費的時間。
◎ 最後,輸出每次搜尋的平均時間,來比較哪種方法更快。
核心比較
◆ 線性搜尋的時間複雜度是 O(n),因為它需要檢查列表中的每個元素。
◆二分搜尋的時間複雜度是 O(log n),因為每次搜尋時,範圍會縮小一半,所以在大列表中它會比線性搜尋快很多。
留言
追蹤
檢舉
上一篇
Day25. 實作練習:圈圈叉叉Tic-Tac-Toe
下一篇
Day27. 實作練習:踩地雷遊戲 Minesweeper
系列文
Python學習馬拉松:30天挑戰
共
30
篇
目錄
RSS系列文
訂閱系列文
2
人訂閱
26
Day26. 實作練習:Binary Search
27
Day27. 實作練習:踩地雷遊戲 Minesweeper
28
Day28. 實作練習:數獨解決器Sudoku Solver
29
Day29. 實作練習:圈圈叉叉Tic-Tac-Toe --AI
30
Day30. 實作練習:馬可夫鏈文本生成器 Markov Chain Text Composer
完整目錄
熱門推薦
{{ item.subject }}
{{ item.channelVendor }}
|
{{ item.webinarstarted }}
|
{{ formatDate(item.duration) }}
直播中
立即報名
尚未有邦友留言
立即登入留言
iThome鐵人賽
參賽組數
902
組
團體組數
37
組
累計文章數
19652
篇
完賽人數
530
人
看影片追技術
看更多
{{ item.subject }}
{{ item.channelVendor }}
|
{{ formatDate(item.duration) }}
直播中
熱門tag
看更多
15th鐵人賽
16th鐵人賽
13th鐵人賽
14th鐵人賽
17th鐵人賽
12th鐵人賽
11th鐵人賽
鐵人賽
2019鐵人賽
javascript
2018鐵人賽
python
2017鐵人賽
windows
php
c#
linux
windows server
css
react
熱門問題
Win2008R2 AD無法派送印表機到 Win11 的電腦,可以用網域內的win11電腦部屬派送至其他成員電腦嗎?
作為新手想踏入MIS領域,應該讀什麼?
清掉所有cookie及暫存資料後,再次登入蝦皮還沒驗手機號前,就已偵測出我的帳號名稱!這是什麼技術?
閱讀 [技術文章] 的需求建議~
google 試算表 App Scripts 問題
OCS Inventory NG
M365 Outlook無法接收到 msa.hinet.net 網域信件
匯入edge系統管理範本後,原本的傳統系統管理範本遺失了
熱門回答
作為新手想踏入MIS領域,應該讀什麼?
M365 Outlook無法接收到 msa.hinet.net 網域信件
清掉所有cookie及暫存資料後,再次登入蝦皮還沒驗手機號前,就已偵測出我的帳號名稱!這是什麼技術?
google 試算表 App Scripts 問題
Win2008R2 AD無法派送印表機到 Win11 的電腦,可以用網域內的win11電腦部屬派送至其他成員電腦嗎?
熱門文章
Day.6 好文件長什麼樣(命名規則・錯誤訊息格式・時間格式 ISO 8601)
Vigor2927 如何使用Windows系統與Vigor路由器建立IKEv2連線,Windows 11 ARM版本 沒辦法安裝 SmartVPN Client
版本控制是什麼?為什麼Git是必學工具?
9種數據分析方法,幫你解決90%的問題
Day 5 🔧 第一次動手:Postman 按按鈕測 2 次 產出:1 份 Collection(站/路線+到站各一支)
IT邦幫忙
×
標記使用者
輸入對方的帳號或暱稱
Loading
找不到結果。
標記
{{ result.label }}
{{ result.account }}