python 基本算法

youngfan007

一.无序表查找　　
def sequential_search(lis, key):
　　
    for i in lis:
　　
        if i == key:
　　
            return lis.index(i)
　　
        else:
　　
            continue
　　
    else:
　　
        return False
　　
if __name__ == '__main__':
　　
    LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
　　
    result = sequential_search(LIST,1231)
　　
    print(result)
　　

　　
二.有序表查找
　　
1.二分查找(Binary Search)
　　
def binary_search(lis,key):
　　
    low = 0
　　
    high = len(lis) - 1
　　
    time = 0
　　
    while low < high:
　　
        time += 1
　　
        mid = int((low + high)/2)
　　
        if key < lis[mid]:
　　
            high = mid - 1
　　
        elif key > lis[mid]:
　　
            low = mid + 1
　　
        else:
　　
            print(&quot;times: %s&quot; % time)
　　
            return mid
　　
    print(&quot;times: %s&quot; % time)
　　
    return False
　　

　　
if __name__ == '__main__':
　　
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
　　
    result = binary_search(LIST,99)
　　
    print(result)
　　

　　
2. 插值查找
　　
二分查找法虽然已经很不错了，但还有可以优化的地方。
　　
有的时候，对半过滤还不够狠，要是每次都排除十分之九的数据岂不是更好？选择这个值就是关键问题，插值的意义就是：以更快的速度进行缩减。
　　
插值的核心就是使用公式：
　　
value = (key – list[low])/(list[high] – list[low])
　　
用这个value来代替二分查找中的1/2
　　
def binary_search(lis, key):
　　
    low = 0
　　
    high = len(lis) - 1
　　
    time = 0
　　
    while low < high:
　　
        time += 1
　　
        # 计算mid值是插值算法的核心代码
　　
        mid = low + int((high - low) * (key - lis[low]) / (lis[high] - lis[low]))
　　
        print(&quot;mid=%s, low=%s, high=%s&quot; % (mid, low, high))
　　
        if key < lis[mid]:
　　
            high = mid - 1
　　
        elif key > lis[mid]:
　　
            low = mid + 1
　　
        else:
　　
            # 打印查找的次数
　　
            print(&quot;times: %s&quot; % time)
　　
            return mid
　　
    print(&quot;times: %s&quot; % time)
　　
    return False