Pythonは二分検索(再帰と非再帰)を実現

二分検索は毎回半分のデータを排除でき,検索の効率は非常に高いが,限界は大きい.二分検索を使用するには、順序付きシーケンスでなければなりません.

1.     

    def binary_search(lis, nun):
        left = 0
        right = len(lis) - 1
        while left <= right:   #    
            mid = (left + right) // 2   #      ，     （        ）
            if num < lis[mid]:  #            ，          ，
                right = mid - 1   #     ，          mid-1
            elif num > lis[mid]:   #            ，          
                left = mid + 1    #     ，          mid+1
            else:
                return mid  #            ，       
        return -1  #      ，       ，      

    lis = [11, 32, 51, 21, 42, 9, 5, 6, 7, 8]
    print(lis)
    lis.sort()
    print(lis)
    while 1:
        num = int(input('       ：'))
        res = binary_search(lis, num)
        print(res)
        if res == -1:
            print('   ！')
        else:
            print('  ！')

2.    

    def binary_search(lis, left, right, num):

        if left > right: #      
            return -1
        mid = (left + right) // 2
        if num < lis[mid]:
            right = mid -1
        elif num > lis[mid]:
            left = mid + 1
        else:
            return mid
        return binary_search(lis, left, right, num)
        #       return         ，    None
        #          ，    return，      None

    lis = [11, 32, 51, 21, 42, 9, 5, 6, 7, 8]
    print(lis)
    lis.sort()
    print(lis)
    while 1:
        num = int(input('       ：'))
        res = binary_search(lis, 0, len(lis)-1,num)
        print(res)
        if res == -1:
            print('   ！')
        else:
            print('  ！')