算法：Sequence Search

站内链接:

Introduction

Intro

线性搜索或顺序搜索是一种寻找某一特定值的搜索算法，指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。是最简单的一种搜索算法.
线性搜索在物理上可以顺序, 也可以连接, 但是逻辑上是顺序存储的. 相比哈希检索, 线性检索的数据没有任何限定, 没有额外的键值空间消耗, 没有唯一值的限定.

Classify

无序表查找: 数据本身没有经过排序, 通过暴力遍历查找数据
有序表查找: 二分查找, 差值查找, 斐波那契查找, 线性索引查找

Order Search

Analysis

检索过程: 针对线性表里的所有记录，逐个进行关键码和给定值的比较

若某个记录的关键码和给定值比较相等，则检索成功
否则检索失败

物理存储: 在物理上可以顺序, 也可以链表存储, 但在逻辑上是顺序存储的

性能分析

使用暴力搜索, 时间复杂度: O(n)

Example

def sequential_search(lis, key):
    for i in range(len(lis)):
        if lis[i] == key:
            return i
    return None


if __name__ == '__main__':
    src = [1, 0, 123, 53, 293, 8, 123, 22, 54, 7, 92, 303, 222]
    index = sequential_search(src, 123)
    if index:
        print('下标:', index, ' 值:', src[index])
    else:
        print('未找到')

Binary Search

Analysis

数据本身在存储或者取出时, 必须先经过排序, 以便在后续的搜索过程中能够更加方便快捷. 一般而言, 在搜索算法中, 都要求数据为静态数据, 不会经常性的进行数据的更新和删除操作. 对于大数据, 如果使用暴力搜索, 性能可能不如想象, 在对已排序数据进行查找时, 则有多种方式:

二分查找: 查找表中不断比较中间元素与查找值，以二分之一的倍率进行表范围的缩小
插值查找: 对半过滤还不够狠, 如果以 10 分之 9 的倍率进行范围缩小, 能够更快的进行缩减, 使用value = (key - list[low])/(list[high] - list[low])公式来完成
斐波那契查找: 利用斐波那契数据列表降低搜索范围

性能分析

时间复杂度: O(logn)

Example

def binary_search(lis, key):
    low = 0
    high = len(lis) - 1
    time = 0

    while low < high:
        time += 1
        # 插值查找算法: low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
        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

    return None


if __name__ == '__main__':
    src = [1, 5, 7, 8, 12, 16, 20, 22, 54, 99, 100, 123, 200, 222, 444]
    result = binary_search(src, 99)
    if result:
        print('下标:', result, ' 查找值:', src[result])
    else:
        print('查找失败')