对排好序的数据进行查找

时间:2021-02-28 11:39:46
二分查找法:
# 对于排好序的数组进行二分查找
def binary_search(needed_data, data_list):
    first = 0
    last = len(data_list) - 1
    times = 0
    # 当数组中最后一个数的序数大于等于第一个数的序数时
    while last >= first:
        times += 1
        mid = (first+last)//2
        if data_list[mid] > needed_data:
            last = mid
        elif data_list[mid] < needed_data:
            first = mid
        else:
            print('被查找的数的序数为'+str(mid))
            print('二分的次数为:'+str(times))
            break
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = 5
binary_search(b, a)
被查找的数的序数为4
times:1

二:拉格朗日查找法

# 对于排好序的数组进行拉格朗日查找
def lagrange_search(needed_data, data_list):
        first = 0
        last = len(data_list) - 1
        times = 0
        # 当数组中最后一个数的序数大于等于第一个数的序数时
        while last >= first:
            times += 1
            date = int((needed_data-first)/(last-first))
            mid = int(first + (last-first)*date)
            if data_list[mid] > needed_data:
                last = mid - 1
            elif data_list[mid] < needed_data:
                first = mid + 1
            else:
                print('被查找的数的序数为' + str(mid))
                print('查找的次数为:' + str(times))
                break
lagrange_search(b,a)