python實現二分查找演算法/二分排序演算法

二分法可以分為三類：二分查找演算法、二分排序演算法、二分合併演算法。

本文分別基於循環和遞歸實現二分查找演算法，然後對比介紹並實現了插入排序演算法和二分排序演算法。

二分查找演算法

二分查找又被稱為折半查找。假設我們有一個列表，要在該列表中查找某一個元素，我們需要先對該列表進行排序（假設是從小到大的排序），然後取這個列表的中值與待查找的元素進行比較，如果該元素等於中值，則查找成功；如果該元素大於中值，則接下來在右邊的子表（之前二分出來的兩個子表中的右邊子表）中繼續進行以中值為中心的折半查找；如果該元素小於中值，則在左邊的子表中繼續進行以中值為中心的折半查找…如此循環，直到查找到目標元素，此時查找成功，或者直到子表再也不能進行二分為止，此時查找不成功。

我們在列表[1,5,9,3,6,12,7,25,10]中查找元素12，其基於循環的python實現如下：

輸出結果為：

當查找元素為key=13時，其輸出結果為：

二分查找演算法直觀上屬於一種「持續的折半查找」，它被層層拆解為一個個子問題，與遞歸的思維非常吻合。所以，我們也完全可以基於遞歸演算法來實現二分查找。

二分查找演算法基於遞歸演算法的python實現如下：

輸出結果為：

可以發現元素12的序號和基於循環的方法不一致，這是因為二分產生的子序列是由原序列切片產生的新序列。

同樣地，當查找元素key=13時，輸出結果為：

即在序列中沒有查找到元素13。

二分排序演算法

前面的文章中我們從撲克牌的排序原理著手，然後用python實現了插入排序。二分排序演算法就是在插入排序的基礎上進行改進的一種演算法，所以二分排序又稱為折半插入排序。

當直接插入排序進行到某一趟時，已經實現了一部分的有序，此時不再繼續使用插入排序演算法，而對前面已經實現有序的部分採用折半二分查找，找出下一個元素應該插入的位置，即一部分的插入排序加上一部分的二分查找插入後續元素，這就是我們所說的折半插入排序，是一種穩定的排序演算法，其元素的比較次數因為採用折半查找而減少。

我們首先得到插入排序演算法的python實現：

輸出結果為：

然後我們對二分排序演算法進行python實現：

輸出結果為：

可見，二分排序演算法同樣實現了符合預期的輸出。

插入排序和二分排序雖然能實現同樣的效果，但它們需要的時間複雜度是不一樣的，我們分別通過如下的計時語句來實現插入排序和二分排序的計時：

當將進行排序的元素個數增大到20000時，可以明顯地觀察到兩種方法的時間對比：

通過結果可知，二分排序方法比插入排序方法快太多！

劉三少爺的劍

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！