python 基本算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
一.无序表查找
def sequential_search(lis, key):
    for in lis:
        if == key:
            return lis.index(i)
        else:
            continue
    else:
        return False
if __name__ == '__main__':
    LIST = [1581232254799300222]
    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("times: %s" % time)
            return mid
    print("times: %s" % time)
    return False
 
if __name__ == '__main__':
    LIST = [1578225499123200222444]
    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("mid=%s, low=%s, high=%s" % (mid, low, high))
        if key < lis[mid]:
            high = mid - 1
        elif key > lis[mid]:
            low = mid + 1
        else:
            # 打印查找的次数
            print("times: %s" % time)
            return mid
    print("times: %s" % time)
    return False              




     本文转自小白的希望 51CTO博客,原文链接:http://blog.51cto.com/haoyonghui/2055623,如需转载请自行联系原作者







上一篇:如何搭建一个属于自己的个人网站


下一篇:SAP Cloud for Customer(C4C)的一些学习资料(持续更新)