演算法 | 二進位搜尋演算法---使用Python3

演算法 | 二進位搜尋演算法---使用Python3

估計會寫一系列以Python 3 為實作的演算法紀錄文章,一方面是作為筆記記錄自己當除如何理解演算法,另一方面是透過輸出(分享),可以增進自己的理解。


二進位搜尋演算法

時間複雜度O(log n),註:此處的log以2為底。
二進位搜尋演算法常跟簡易搜尋演算法做比較,透過時間複雜度O的不同,理解處理速度的不同,如下表所示:

時間複雜度O演算法
O(log n)二進位搜尋法
O(n)簡易搜尋法
n為項目數。


例如要搜尋一串數列,數值介於1~100,那項目數n有100個,使用二進位搜尋演算法最壞的情況下所需時間為log100(log以2為底)次,簡易搜尋法最壞的情況下所需時間為100次。

而二進位搜尋法在搜尋數值1~100,每次都是對半切,第一次搜尋50,若是太高,就搜尋1~49;若是太低,就搜尋51~100,不斷的對半切,直到找出數值。



實作程式



轉貼本文時,需註明來自黑修斯的隨手札記原創作者 hughes chen(黑修斯),及附上原文連結,同時 禁止修改,禁止商業使用 。

張貼留言

0 留言