Python資料結構與算法（18）---檢索算法

目錄

• 檢索算法
• 線性查找
• • 圖解線性查找
  • 實戰：線性查找

資料結構的排序算法，到17篇歸并排序就徹底講解完成。從今天開始，我們将進入全新的資料結構知識，它的名字叫查找算法，也叫檢索算法。

檢索算法又分為排序檢索與非排序檢索。排序檢索顧名思義就是先排序在進行查找，在資料庫的查找中，我們往往都是這麼做的。當然非排序檢索也存在，隻不過效率非常低。

檢索算法包括線性查找、二分查找、插值查找、斐波拉契查找、分塊查找、哈希查找以及回溯查找7個算法。是以，從18到24篇都是檢索算法的内容知識。

下面，我們來介紹今天第1個要講解的查找算法：線性查找。

線性查找，又名Linear Search，顧名思義就是一種順序的查找方算法，也是所有查找算法中最簡單的一個算法。

其具體的原理：從第1個元素開始依次查找比較，若查找成功，傳回其元素的索引；若查找失敗，則傳回查詢無果。

當然，線性查找即可以從數列左邊開始，也可以從數列右邊開始。同時，它的原始資料既可以是排序好的清單，也可以是非排序清單。

還是與前面的排序算法一樣，我們也将查找算法用圖解的方式給大家一一展示出來，這樣更友善初學者的了解與學習，具體原理圖解圖下：

如上圖所示，我們在該清單中查詢元素等于3的索引位置。這裡，我們從左邊i=0開始查找，如果查找成功，則傳回對應的索引位置。

因為線性查找太過于簡單，我們這裡實作2中線性查找，一種是從左邊開始查找，一種是從右邊開始查找。具體示例如下：

# 從左線性查找
def lef_linear_search(my_list, num):
    n = len(my_list)
    i = 0
    while i < n:
        if my_list[i] == num:
            return i
        i += 1
    return "None"


# 從右線性查找
def right_linear_search(my_list, num):
    n = len(my_list)
    i = n - 1
    while i >= 0:
        if my_list[i] == num:
            return i
        i -= 1
    return "None"


if __name__ == "__main__":
    my_list = [8, 0, 4, 3, 2, 1]
    print("線性查找的原始數列：", my_list)
    print("從左邊開始線性查找：", lef_linear_search(my_list, 3))
    print("從右邊開始線性查找：", lef_linear_search(my_list, 3))