資料結構與算法 7.順序查找和二分法查找

查找

常見查找算法：順序查找，二分法，二叉樹，哈希

選擇查找方法需要考慮的因素：
    查找速度
    應用場景
    資源占用

資料結構相關性：讨論查找算法的時候，首先要明确是在什麼資料結構上執行查找算法
               不同的資料結構有不同的查找算法，有的資料結構就是為了查找而生，如二叉樹、哈希
           

順序查找

周遊序列，将序列中的元素與被查找的資料逐一作比較
順序查找對被檢索的序列沒有任何要求

複雜度：時間複雜度：O(n)
           

二分法 binarySearch

二分法隻适用于已經完成排序的序列
通過把序列中間的數與被查找的資料不斷作比較來确定被查找的數所處的範圍

複雜度：最優時間複雜度：O(1)
        最差時間複雜度：O(logn)
           

方法一

def binary_search1(varlist,item):
    # 首尾兩個位置
    first = 0
    last = len(varlist) - 1

    # first=last時還剩最後一個值，是以還需要比較
    while first <= last :
        # 根據首尾找到中間位置
        midpoint = (first + last) // 2
        if item == varlist[midpoint] :
            return True
        # 被查找元素小于中間的數，則改變last，在左邊繼續二分
        elif item < varlist[midpoint] :
            last = midpoint - 1
        # 被查找元素大于中間的數，則改變first，在右邊繼續二分
        elif item > varlist[midpoint] :
            first = midpoint + 1
    return False
varl = [3,15,26,57,78,128,258,438]
res = binary_search1(varl,57)
print(res)

True
           

方法二：遞歸

def binary_search2(varlist,item):
    # 結束遞歸的條件，比較完序列中所有元素
    if len(varlist) == 0 :
        return False
    else:
        # 找到中間位置
        midpoint = len(varlist) // 2
        if item == varlist[midpoint] :
            return True
        # 調用自身來修改查找範圍
        elif item < varlist[midpoint] :
            return binary_search2(varlist[:midpoint],item)
        else :
            return binary_search2(varlist[midpoint+1:],item)
varl = [3,15,26,57,78,128,258,438]
res = binary_search2(varl,3)
print(res)

True