【数据结构】八个常用查找算法

0、Github源代码地址分享

https://github.com/ShaShiDiZhuanLan/Demo_SortSearch_Python

1、顺序查找

1.1 简介

最基础的遍历无序列表的查找算法
顺序查找又称为线性查找，是一种最简单的查找方法。
适用于线性表的顺序存储结构和链式存储结构。
该算法的时间复杂度为O(n)

1.2 基本思路

从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

1.3 优缺点

优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。
缺点：是当n 很大时，平均查找长度较大，效率低；

1.4 源代码

# 作者：沙振宇
# 最基础的遍历无序列表的查找算法
# 时间复杂度O(n)

# 顺序查找(线性查找)
def sequential_search(list, key):
    length = len(list)
    print("length:%s list:%s"%(length,list))
    for i in range(length):
        if list[i] == key:
            return i
    return False

if __name__ == '__main__':
    list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
    result = sequential_search(list, 22)
    print("List key is:", result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.5 效果

2、二分查找

2.1 简介

二分查找（Binary Search），是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种查找算法每一次比较都使查找范围缩小一半。

2.2 复杂度分析

时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn)
空间复杂度：O(1)
最优时间复杂度：O(1)
最坏时间复杂度：O(logn)

2.3 源代码

# 作者：沙振宇
# 针对有序查找表的二分查找算法
# 1. 二分查找是有条件的，首先是有序，其次因为二分查找操作的是下标，所以要求是顺序表
# 2. 最优时间复杂度：O(1)
# 3. 最坏时间复杂度：O(logn)

# 二分查找
def binary_search(list, key):
    length = len(list)
    first = 0
    last = length - 1
    print("length:%s list:%s"%(length,list))
    while first <= last:
        mid = (last + first) // 2
        if list[mid] > key:
            last = mid - 1
        elif list[mid] < key:
            first = mid + 1
        else:
            return mid
    return False

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = binary_search(list, 54)
    print("List key is:", result)
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

2.4 效果

3、分块查找

3.1 简介

要求是顺序表，分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

3.2 算法思想

将n个数据元素"按块有序"划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须"按块有序"；
即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
而第2块中任一元素又都必须小于第3块中的任一元素，……

3.3 算法流程

1、先选取各块中的最大关键字构成一个索引表；
2、查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
3、在已确定的块中用顺序法进行查找。

3.4 复杂度分析

时间复杂度：O(log(m)+N/m)

3.5 源代码

# 作者：沙振宇
# 时间复杂度：O(log(m)+N/m)
# 1、先选取各块中的最大关键字构成一个索引表
# 2、查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中
# 3、在已确定的块中用顺序法进行查找

# 二分查找
def binary_search(list, key):
    length = len(list)
    first = 0
    last = length - 1
    print("length:%s list:%s"%(length,list))
    while first <= last:
        mid = (last + first) // 2
        if list[mid] > key:
            last = mid - 1
        elif list[mid] < key:
            first = mid + 1
        else:
            return mid
    return False

# 分块查找
def block_search(list, count, key):
    length = len(list)
    block_length = length//count
    if count * block_length != length:
        block_length += 1
    print("block_length:", block_length) # 块的多少
    for block_i in range(block_length):
        block_list = []
        for i in range(count):
            if block_i*count + i >= length:
                break
            block_list.append(list[block_i*count + i])
        result = binary_search(block_list, key)
        if result != False:
            return block_i*count + result
    return False

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = block_search(list, 4, 444) # 第二个参数是块的长度，最后一个参数是要查找的元素
    print("List key is:", result)
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

3.6 效果

4、斐波那契查找

4.1 简介

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，
在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。
该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

4.2 算法描述

斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。
在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，
则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，
后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。

4.3 复杂度分析

最坏情况下，
时间复杂度为O(log2n)，
且其期望复杂度也为O(log2n)。

4.4 源代码

# 作者：沙振宇
# 斐波那契查找算法
# 时间复杂度O(log(n))

# 斐波那契查找算法
def fibonacci_search(list, key):
    length = len(list)
    # 需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。
    F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368]
    low = 0
    high = length - 1
    print("length:%s list:%s"%(length,list))

    # 为了使得查找表满足斐波那契特性，在表的最后添加几个同样的值
    # 这个值是原查找表的最后那个元素的值
    # 添加的个数由F[k]-1-high决定
    k = 0
    while high > F[k] - 1:
        k += 1
    i = high
    while F[k] - 1 > i:
        list.append(list[high])
        i += 1
    time = 0 # 算法主逻辑。time用于展示循环的次数。
    while low <= high:
        time += 1
        # 为了防止F列表下标溢出，设置if和else
        if k < 2:
            mid = low
        else:
            mid = low + F[k - 1] - 1
        if key < list[mid]:
            high = mid - 1
            k -= 1
        elif key > list[mid]:
            low = mid + 1
            k -= 2
        else:
            if mid <= high:
                return mid
            else:
                return high
    return False

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = fibonacci_search(list, 7)
    print("List key is:", result)
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

4.5 效果

5、哈希查找

5.1 简介

哈希表就是一种以键-值(key-indexed) 存储数据的结构，只要输入待查找的值即key，即可查找到其对应的值。

5.2 算法思想

哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：
将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。
这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

5.3 算法流程

1）用给定的哈希函数构造哈希表；
2）根据选择的冲突处理方法解决地址冲突；常见的解决冲突的方法：拉链法和线性探测法。
3）在哈希表的基础上执行哈希查找。

5.4 复杂度分析

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

5.5 源代码

# 作者：沙振宇
# 单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

# 除法取余法实现的哈希函数
def myHash(data, hashLength):
    return data % hashLength

# 哈希表检索数据
def searchHash(hash, hashLength, data):
    hashAddress = myHash(data, hashLength)
    while hash.get(hashAddress) and hash[hashAddress] != data:#指定hashAddress存在，但并非关键值，则用开放寻址法解决
        hashAddress += 1
        hashAddress = hashAddress % hashLength
    if hash.get(hashAddress) == None:
        return False
    return hashAddress

# 数据插入哈希表
def insertHash(hash, hashLength, data):
    hashAddress = myHash(data, hashLength)
    while(hash.get(hashAddress)):#如果key存在说明应经被别人占用,需要解决冲突
        hashAddress += 1 #用开放寻执法
        hashAddress = myHash(hashAddress, hashLength)
    hash[hashAddress] = data

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    hashLength = len(list) + 1
    hash = {}
    print("length:%s list:%s"%(hashLength,list))
    for i in list:
        insertHash(hash, hashLength, i)
    result = searchHash(hash, hashLength, 1)
    print("List key is:", result)
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

5.6 效果

6、插值查找

6.1 简介

插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，其核心就在于插值的计算公式 (key-a[low])/(a[high]-a[low])*(high-low)。
时间复杂度o(logn)但对于表长较大而关键字分布比较均匀的查找表来说，效率较高。

6.2 算法思想

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

6.3 复杂度分析

时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要 O（n）。
空间复杂度：O（1）。

6.4 源代码

# 作者：沙振宇
# 时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要 O（n）。
# 空间复杂度：O（1）。

# 插值查找算法
def interpolation_search(list, key):
    length = len(list)
    low = 0
    high = length - 1
    time = 0
    print("length:%s list:%s"%(length,list))
    while low < high:
        time += 1
        mid = low + int((high - low) * (key - list[low]) / (list[high] - list[low]))# 计算mid值是插值算法的核心代码
        if key < list[mid]:
            high = mid - 1
        elif key > list[mid]:
            low = mid + 1
        else:
            return mid
    return False

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = interpolation_search(list, 7)
    print("List key is:", result)
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

6.5 效果

7、B树查找

7.1 简介

一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
树中每个节点至多有m棵子树
若根结点不是叶子节点，那么至少有两棵子树
除根之外的所有非终端节点至少有【m/2】（不小于m/2的最小整数）棵子树
所有叶子节点都在同一层次上

7.2 应用

如果内存和外存交换数据频繁，就会造成时间效率的瓶颈，在一个典型的B树中，如果数据量很大，无法一次性存入内存，
则可以对B树的阶数进行调整，使其与硬盘存储的页面大小相匹配，高度为h，让B树的根节点持久地保留在内存中，
那么在这棵树上寻找一个关键字至多需要读取磁盘h次。

7.3 源代码

# 作者：沙振宇
# B树查找

inorder_find = False
rinorder_find = False

#B树
class BTree:
    def __init__(self,value):
        self.left=None
        self.data=value
        self.right=None
        self.inorder_find = False
        self.rinorder_find = False

    def insertLeft(self,value):
        self.left=BTree(value)
        return self.left

    def insertRight(self,value):
        self.right=BTree(value)
        return self.right

    def show(self):
        print(self.data)

# 插入数据
def insert(node,value):
    if value > node.data:
        if node.right:
            insert(node.right,value)
        else:
            node.insertRight(value)
    else:
        if node.left:
            insert(node.left,value)
        else:
            node.insertLeft(value)

#中序遍历：先左子树，再根节点，再右子树 从小到大排序
def inorder(node, key):
    if node.data:
        if node.left:
            inorder(node.left, key)
        node.show()
        if node.data == key:
            global inorder_find
            print("_______________________find it %s_______________________"%key)
            inorder_find = True
        if node.right:
            inorder(node.right, key)

#倒中序遍历 从大到小排序
def rinorder(node, key):  #倒中序遍历
    if node.data:
        if node.right:
            rinorder(node.right, key)
        node.show()
        if node.left:
            rinorder(node.left, key)
        if node.data == key:
            global rinorder_find
            print("_______________________find it %s_______________________"%key)
            rinorder_find = True

if __name__ == "__main__":
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    key = 222
    node = BTree(list[0])
    for i in range(1,len(list)):
        insert(node,list[i])
    print("key: %s\nLength: %s\nList: %s"%(key, len(list), list))

    inorder(node,key)
    print("________________________inorder List key is:", inorder_find)

    rinorder(node,key)
    print("________________________rinorder List key is:", rinorder_find)
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

7.4 效果

8、二叉树查找（BST）

8.1 简介

二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。
这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

8.2 算法思想

二叉查找树（BinarySearch Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。

8.3 性质

对二叉查找树进行中序遍历，即可得到有序的数列。

8.4 复杂度分析

它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。
原因在于插入和删除元素的时候，树没有保持平衡。

8.5 源代码

# 作者：沙振宇
# ----- 二叉树查找（BST） -----
# 1、广度优先BFS--查找
# 2、前序遍历--查找
# 3、中序遍历--查找
# 4、后序遍历--查找

class Node(object):
    def __init__(self, element, lchild=None, rchild=None):
        self.element = element
        self.lchild = lchild
        self.rchild = rchild

class Tree(object):
    def __init__(self, root=None):
        self.list = []
        self.root = root
        self.preorder_find = False
        self.inorder_find = False
        self.postorder_find = False
    # 增加树节点
    def add(self, item):
        self.list.append(item)
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        else:
            queue = []
            queue.append(self.root)
            while queue:
                cur_node = queue.pop()
                if cur_node.lchild is None:
                    cur_node.lchild = node
                    return
                elif cur_node.rchild is None:
                    cur_node.rchild = node
                    return
                else:
                    queue.append(cur_node.lchild)
                    queue.append(cur_node.rchild)
    # 广度优先BFS
    def width_circle(self, key):
        if self.root is None:
            return ' '
        else:
            queue = []
            queue.append(self.root)
            while queue:
                cur_node = queue.pop()
                print(cur_node.element, end=' ')
                if cur_node.element == key:
                    return True
                if cur_node.lchild is not None:
                    queue.append(cur_node.lchild)
                if cur_node.rchild is not None:
                    queue.append(cur_node.rchild)
        return False
    # 前序遍历
    def preorder(self, node, key):
        if node == None:
            return
        print(node.element, end=' ')
        self.preorder(node.lchild, key)
        self.preorder(node.rchild, key)
        if node.element == key:
            print("\n_______________________find it:%s_______________________"%key)
            self.preorder_find = True
    # 中序遍历
    def inorder(self, node, key):
        if node == None:
            return
        self.inorder(node.lchild, key)
        print(node.element, end=' ')
        if node.element == key:
            print("\n_______________________find it:%s_______________________"%key)
            self.inorder_find = True
        self.inorder(node.rchild, key)
    # 后序遍历
    def postorder(self, node, key):
        if node == None:
            return
        self.postorder(node.lchild, key)
        self.postorder(node.rchild, key)
        print(node.element, end=' ')
        if node.element == key:
            print("\n_______________________find it:%s_______________________"%key)
            self.postorder_find = True

if __name__ == '__main__':
    t = Tree()
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    key = 12
    for item in list:
        t.add(item)
    print("Length: %s\nList: %s"%(len(list),list))

    print("\n广度优先BFS:")
    result = t.width_circle(key)
    print("\nList key is:", result)

    print("\n前序遍历:")
    t.preorder(t.root, key)
    print("\nList key is:", t.preorder_find)

    print("\n中序遍历")
    t.inorder(t.root, key)
    print("\nList key is:", t.inorder_find)

    print("\n后序遍历")
    t.postorder(t.root, key)
    print("\nList key is:", t.postorder_find)
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

8.6 效果

9、其它算法

还有一些其它查找算法，比如：（平衡查找树）红黑树查找、（平衡查找树）B+树查找、（平衡查找树）2-3树等，暂时先写这8种查找，用到比较多的是二分法查找，一定要学会哟。