经典算法之搜索

发表于 更新于
搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找。

搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找。

1、顺序查找

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法，顺序查找是最简单的搜索算法。当数据量很大时，平均查找长度较大，效率低。

1
2
3
4
5
6
7
8
9
10
11
12
def sequential_search(nums, target):
    for i in nums:
        if i == target:
            return i
    else:
        return -1

if __name__ == '__main__':
    sorted_nums = list(range(1, 11))
    n = 6

    print(sequential_search(sorted_nums, n))

2、二分法查找

二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

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
def bin_search_recursively(nums, target):
    '''
    二分查找(递归版)
    '''
    left, right = 0, len(nums) - 1  # 确定查找的上下界
    def helper(nums, left, right, target):
        if left > right:
            return -1  # 执行结束但是没有找到
        mid = (left + right) // 2
        if nums[mid] < target:
            return helper(nums, mid + 1, right, target)
        elif nums[mid] > target:
            return helper(nums, left, mid - 1, target)
        else:
            return mid
    return helper(nums, left, right, target)  

def bin_search_nonrecursively(nums, target):
    '''
    二分查找(非递归版)
    '''
    left, right = 0, len(nums) - 1  # 确定查找的上下界
    while left <= right:  # 当left == right时还剩下最后一个值需要进行检验
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # +1是因为mid已经验证过不符合条件，新的区间又mid+1开始
        elif nums[mid] > target:
            right = mid - 1 # 这里+1同上面原因相同
        else:
            return mid
    return -1  # 执行结束但是没有找到

if __name__ == '__main__':
    sorted_nums = list(range(1, 11))
    n1 = 12
    n2 = 6

    print(bin_search_nonrecursively(sorted_nums, n1))
    print(bin_search_nonrecursively(sorted_nums, n2))
    print(bin_search_recursively(sorted_nums, n1))
    print(bin_search_recursively(sorted_nums, n2))

3、二叉树查找

二叉查找树（Binary Search Tree），又称为二叉搜索树、二叉排序树。其或者是一棵空树；或者是具有以下性质的二叉树： 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(nums, target):
    mid = (len(nums)) // 2
    if len(nums) == 0:
        return -1
    elif nums[mid] == target: 
        return mid
    elif nums[mid] > target:
        return binary_search(nums[:, mid], target)
    else:
        return binary_search(nums[mid + 1:], target)

if __name__ == '__main__':
    sorted_nums = list(range(1, 11))
    n1 = 6
    n2 = 60

    print(binary_search(sorted_nums, n1))
    print(binary_search(sorted_nums, n2))

4、哈希查找（散列查找）

哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像)。如果数据本身是无法排序的，就不能对它们进行比较查找。
如果数据是很难比较的，即使采用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。
在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。

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
def myHash(target, hashLength):
    '''
    除法取余法实现的哈希函数
    '''
    return target % hashLength

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

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

if __name__ == '__main__':
    hashLength = 20
    L = [13, 29, 27, 28, 26, 30, 38 ]
    hash={}
    for i in L:
        insertHash(hash,hashLength,i)
    result = searchHash(hash,hashLength,38)
    if result:
        print("数据已找到，索引位置在",result)
        print(hash[result])
    else:
        print("没有找到数据")