定义

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法。

注:定义来自百度百科。

在学习算法的时候,需要学会理解算法是如何实现的,掌握其算法的原理,以及如何判断算法的优越性。

我们将在接下来的内容,逐步理解这些简单的搜索算法。

补充概念

算法复杂度:指算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。时间资源用时间复杂度表示,空间资源用空间复杂度表示。

时间复杂度:抛开与计算机硬件、软件有关的因素,一个程序的运行时间依赖于算法的好坏和问题的输入规模。语句总的执行次数 T(n)是关于问题规模 n 的函数,进而分析 T(n)随 n 的变化情况并确定 T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n)),在计算机科学,称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

空间复杂度:空间复杂度简单来说就是这段代码占内存的大小,它与时间复杂度都是用 O 表示法。在现代计算机科学,计算机的内存基本满足需求,所以采用[空间换时间]的办法,我们在考察一个算法优劣,一般只关注时间复杂度。

最坏复杂度:最坏时间复杂度,简称最坏复杂度。

最好复杂度:最好时间复杂度,简称最好复杂度。

平均复杂度:平均时间复杂度,简称平均复杂度。

顺序搜索

顺序搜索也称为线性搜索,属于无序查找算法。

算法原理

思路:从数据结构线性表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值 k 相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于 k 的结点,表示查找失败。

适用性:顺序搜索适合于存储结构为顺序存储或链接存储的线性表。

复杂度分析
最坏复杂度: 从一个线性表依次查找对应项,需要做 n 次查找,在最后一项才查找到对应项或者查找失败(仍然未查找到对应项),时间复杂度为 O(n)。

最好复杂度: 从一个线性表依次查找对应项,第一项就查找到对应项,时间复杂度为 O(1)。

平均复杂度: 假设每个数据元素的概率相等(1/n),1/n(1+2+3+...+n)=(n+1)/2,所以时间复杂度为 O(n)。

从顺序表的头部依次遍历元素,判断是否匹配,若匹配则查找成功,若不匹配则遍历下一个元素。

def sequence_search(sequence, target):
    for i in range(len(sequence)):
        if target==sequence[i]:
            return i
    return None

if __name__ == '__main__':
    sequence=[99,12,33,74,521,13,14]
    target=521
    print(sequence_search(sequence,target))
def binary_search(sorted_sequence, target):
    left = 0
    right = len(sorted_sequence)-1
    while(left <= right):
        midpoint = (left+right)//2
        current_item = sorted_sequence[midpoint]
        if current_item == target:
            return midpoint
        elif target < current_item:
            right = midpoint - 1
        else:
            left = midpoint + 1
    return None


if __name__ == '__main__':
    sorted_sequence = [i for i in range(1, 999, 2)]
    print(binary_search(sorted_sequence, target=521))