Python二分法查找的原理和各種實作方案

"""
二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入删除困難。是以，折半查找方法适用于不經常
變動而查找頻繁的有序清單。首先，假設表中元素是按升序排列，将表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間
位置記錄将表分成前、後兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找
到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
"""

#非遞歸實作，查找到傳回True，找不到傳回False
def binary_search1(mlist,item):
    first = 0
    last = len(mlist) - 1

    while first <= last:
        middle = (first + last) // 2
        if item == mlist[middle]:
            return  True
        elif item < mlist[middle]:
            last = middle - 1
        else:
            first = middle + 1
    return False


#遞歸實作，查找到傳回True，找不到傳回False
def binary_search2(mlist,item):
    if len(mlist)==0:
        return False
    else:
        middle = len(mlist)//2
        if item == mlist[middle]:
            return True
        else:
            if item < mlist[middle]:
                return  binary_search2(mlist[:middle],item)
            else:
                return  binary_search2(mlist[middle+1:],item)


#非遞歸實作，查找到傳回元素索引，如果相同元素有多個(相鄰)，則傳回哪個索引不固定，找不到傳回-1
def binary_search3(mlist,item):
    first = 0
    last = len(mlist) - 1

    while first <= last:
        middle = (first + last) // 2
        if item == mlist[middle]:
            return  middle
        elif item < mlist[middle]:
            last = middle - 1
        else:
            first = middle + 1
    return -1


#遞歸實作，查找到傳回元素索引，如果相同元素有多個(相鄰)，則傳回哪個索引不固定，找不到傳回-1
def binary_search4(mlist,item,first,last):
    if first > last:
        return -1
    else:
        middle = (first+last)//2
        if item == mlist[middle]:
            return middle
        else:
            if item < mlist[middle]:
                return  binary_search4(mlist,item,first,middle-1)
            else:
                return  binary_search4(mlist,item,middle+1,last)

if __name__ == '__main__':
    my_list = [1, 15,18, 28, 35,44, 50,77, 88, 96, 98]
    print(binary_search1(my_list,98))
    print(binary_search1(my_list, 70))

    print(binary_search2(my_list, 98))
    print(binary_search2(my_list, 70))

    print(binary_search3(my_list, 88))
    print(binary_search3(my_list, 70))

    print(binary_search4(my_list, 15,0,len(my_list)))
    print(binary_search4(my_list, 70,0,len(my_list)))