Python 學習筆記 : 在串列中搜尋資料

本篇主要是閱讀借自母校的幾本 Python 基礎書籍後所整理的搜尋測試紀錄, 參考書目 : 

# Python零基礎入門班 : 一次打好程式設計與邏輯訓練基本功! 

資料搜尋是序列型態常見的操作, 以下是 Python 中常用的搜尋方式 : 

1. 使用 index() 方法搜尋 : 

Python 的串列 (list) 與元組 (tuple) 物件都內建了 index() 方法, 傳入欲搜尋的元素會傳回該元素之索引, 但若該元素不存在則會出現 ValueError 錯誤, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]      

>>> lot.index(34)                    # 元素存在傳回索引

1

>>> lot.index(27)                    # 元素存在傳回索引

5

>>> lot.index(6)                      # 元素不存在會出現錯誤

Traceback (most recent call last):

  File "<pyshell>", line 1, in <module>

ValueError: 6 is not in list

故使用 index() 搜尋資料必須做例外處理, 例如 : 

>>> lot=[2, 34, 16, 7, 18, 27]   

>>> try:   

    print(f'index={lot.index(5)}') 

except Exception:                           # 或 ValueError

    print(f'not found!')    

not found!  

>>> try:   

    print(f'index={lot.index(27)}')     

except Exception:                           # 或 ValueError

    print(f'not found!')  

index=5

可以將此搜尋功能寫成一個 search() 函式, 傳入序列物件與搜尋標的後會傳回索引 (有找到) 或 None (沒找到), 例如 : 

>>> def search(series, target):     

    try:  

        index=series.index(target)    

        return index     

    except ValueError:    

        return None    

    

>>> lot=[2, 34, 16, 7, 18, 27] 

>>> search(lot, 27)                   # 有找到 : 傳回索引

5

>>> search(lot, 2)                     # 有找到 : 傳回索引

0

>>> if not search(lot, 21):        # 沒找到 : 傳回 None

    print('not found')    

    

not found

2. 使用迴圈循序搜尋 : 

此方法以迴圈從序列物件的開頭依序搜尋標的, 此法缺點是效率較差, 若標的是在序列的最尾端, 則花費的搜尋時間最多. 可將此程序寫成函式, 找到標的時傳回索引, 否則傳回 None, 例如 :

>>> def search(series, target):    

    index=None                                    # 傳回索引初始值

    for i in range(len(series)):             # 以迴圈走訪序列中的元素

        if series[i]==target:                    # 比對是否為找尋之標的

            index=i                                    # 找到就將傳回值設為目前索引

            break                                       # 中止搜尋

    return index                                   # 傳回索引或 None

>>> search(lot, 2)                               # 有找到 : 傳回索引

0   

>>> search(lot, 27)                             # 有找到 : 傳回索引

5   

>>> print(search(lot, 21))                  # 沒找到 : 傳回 None

None

可見功能與上面用 index() 方法實作的一樣. 

3. 使用二分搜尋法 : 

二元搜尋法的對象必須是已排序 (從小至大) 的序列物件 (list 或 tuple), 它的搜尋作法是先將這由小到大排序的序列中間切開分成兩半, 左半部是較小的部分, 右半部是較大的部分. 然後將正中央的元素與搜尋標的比較, 如果相同就是找到了標的, 可結束搜尋; 否則就要看標的比正中央元素大還是小, 若是比正中央元素大, 那就到右半部繼續搜尋, 反之就到左半部繼續搜尋.

串列由小到大排序可用內建函式 sort(), 此函式會改變原本的串列內容, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]    

>>> lot.sort()      

>>> lot     

[2, 7, 16, 18, 27, 34]    

如果要自行實作排序, 可以使用最簡單的氣泡排序, 參考 :

# Python 學習筆記 : 排序之 (一) 氣泡排序

以下是寫成函式的氣泡排序 :

>>> def bubble_sort(arr):   

    for i in range(len(arr)-1, -1, -1):     

        for j in range(i):   

            if arr[j] > arr[j+1]:    

                arr[j], arr[j+1]=arr[j+1], arr[j]   

>>> lot=[2, 34, 16, 7, 18, 27]   

>>> bubble_sort(lot)   

>>> lot     

[2, 7, 16, 18, 27, 34]   

排序好後就可以開始實作二元搜尋法, 寫成函式如下 :

>>> def binary_search(series, target):    

    index=None    

    min=0   

    max=len(series) - 1       

    cnt=0   

    while min <= max:   

        mid=int((min + max )/2)   

        cnt += 1   

        if series[mid]==target:      

            index=mid     

            break      

        elif series[mid]>target:      

            max=mid - 1   

        else:   

            min=mid + 1  

    return index   

>>> lot=[2, 34, 16, 7, 18, 27]   

>>> lot.sort()   

>>> lot   

[2, 7, 16, 18, 27, 34]

>>> binary_search(lot, 27)        

4

>>> binary_search(lot, 7)   

1

>>> binary_search(lot, 34)   

5

>>> print(binary_search(lot, 21))   

None

從程式碼長度來看, 似乎是用 index() 加上 try except 例外處理比較簡單.