黑马程序员技术交流社区

标题: 【上海校区】搜索算法 in Python [打印本页]

---

作者: 不二晨    时间: 2019-3-25 10:42
标题: 【上海校区】搜索算法 in Python
介绍

本节内容将介绍几种常见的搜索算法（主要包含顺序搜索，二分搜索，插值搜索，跳越搜索，快速搜索，哈希搜索）的算法原理，算法复杂度的分析，以及如何实现。

知识点

顺序搜索
二分搜索
插值搜索
跳越搜索
快速搜索
哈希搜索
搜索算法

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

注：定义来自百度百科。

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

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

补充概念

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

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

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

最坏复杂度：最坏时间复杂度，简称最坏复杂度

最好复杂度：最好时间复杂度，简称最好复杂度

平均复杂度：平均时间复杂度，简称平均复杂度

顺序搜索

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

算法原理

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

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

复杂度分析

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

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

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

实现

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

def sequencesearch(sequence,target):
    for i in range(len(sequence)):
        if target==sequence:
            return i
    return None
二分搜索

二分搜索也称折半搜索（Binary Search），它是一种效率较高的搜索方法。但是，二分搜索要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

注：定义来自百度百科。

算法原理

适用性： 二分查找的前提是有序表存储，如果是无序的则先要进行排序操作。对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

基本思想： 用给定值 k 先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析

总共有 n 个元素。

第 1 次折半：还剩 n/2 个元素

第 2 次折半：还剩 n/4 个元素

第 3 次折半：还剩 n/8 个元素

……

第 k 次折半：还剩 n/2^k 个元素

最坏的情况下，最后还剩 1 个元素，令 n/2^k = 1。得 k=logn。时间复杂度 O(logn)

最坏复杂度:上述分析可以得到时间复杂度为 O(logn)

最好复杂度：第一次折半就查找到中间元素,时间复杂度为 O(1)

平均复杂度:时间复杂度为 O(logn),证明如下



实现

思路：每次查询查找范围内的"中间位置"的结点，若该节点不是所需，则缩小查找范围为前半部分或后半部分。

def binarysearch(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
拓展

三分搜索：就是在二分搜索的基础上，将区间分为三个区间做判断，因此存在 5 个条件判断。

def ternary_search(sorted_sequence,target):
    left=0
    right=len(sorted_sequence)-1
    while(left<=right):
        Third1=(right-left)//3+left
        Third2=2*(right-left)//3+left
        if(sorted_sequence[Third1]==target):
            return Third1
        elif(sorted_sequence[Third2]==target):
            return Third2
        elif(target<sorted_sequence[Third1]):
            right=Third1-1
        elif(target>sorted_sequence[Third2]):
            left=Third2+1
        else:
            left=Third1+1
            right=Third2-1
    return None
插值搜索

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。同样的，比如要在取值范围 1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找 5，我们自然会考虑从数组下标较小的开始查找。经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：mid=(left+right)/2, 即 mid=left+1/2*(right-left)

通过类比，我们可以将查找的点改进为如下： mid=left+(key-a[left])/(a[right]-a[left])*(right-left)，也就是将上述的比例参数 1/2 改进为自适应的，根据关键字在整个有序表中所处的位置，让 mid 值的变化更靠近关键字 key，这样也就间接地减少了比较次数。

算法原理

适用性： 对于表长较大，而关键字分布又比较均匀的查找表来说，插值搜索算法的平均性能比折半搜索要好的多。反之，数组中如果分布非常不均匀，那么插值搜索未必是很合适的选择

基本思想： 基于二分搜索算法，只是在取"中点"的时候把比例参数 1/2 修改为自适应参数，可以提高搜索效率。当然，差值搜索也属于有序搜索

复杂度分析

最坏复杂度:时间复杂度为 O(logn)，最坏的情况就是二分搜索的情况，时间复杂度和二分搜索的时间复杂度相同。

最好复杂度：时间复杂度为 O(1)

平均复杂度:时间复杂度为 O(loglogn),证明如下

插值搜索的时间复杂度证明

实现

思路：与二分搜索类似，只是把比例参数 1/2 修改为自适应参数

def insertsearch(sorted_sequence,target):
    left=0
    right=len(sorted_sequence)-1
    while(left<=right):
        midpoint=left+((target-sorted_sequence[left])*(right-left))//(sorted_sequence[right]-sorted_sequence[left]) #比例参数修改
        if midpoint<0 or midpoint>=len(sorted_sequence):
            return None
        current_item=sorted_sequence[midpoint]
        if current_item==target:
            return midpoint
        elif target<current_item:
            right=midpoint-1
        else:
            left=midpoint+1
    return None
跳跃搜索

跳越搜索(Jump search),按照固定步长，从有序表的首项步进，直到匹配到符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置。

跳越搜索的思路如下：给定大小 n 的有序数组 a，目标元素为 x 和跳跃的步长 m ，然后搜索 a[0],a[1],a[2],a[3]...a[km]...一旦我们找到区间 a[km]< target < a[(k+1)m],然后在此区间进行线性搜索找到目标元素 x 的确切位置。

在最坏的情况下，我们必须进行 n/m 跳转，如果最后一个检查值大于要搜索的元素，则我们对线性搜索进行 m-1 比较。因此，最坏情况下的比较总数将为((n/m)+m-1)。当 m =n^(1/2)时，函数((n/m)+m-1)的值将为最小值。因此，最好的步长是 m=n^(1/2)

算法原理

适用性： 跳越搜索的前提是有序表存储。相比于二分搜索，跳跃搜索仅遍历一次，而二分搜索最多需要 O(logn)，如果向后跳跃比向前跳跃花费更多时间，考虑要搜索的元素是最小元素或小于最小的，我们一般选用跳越搜索。

基本思想： 基于二分搜索算法，采用固定间隔进行跳越，直到找到一个符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置。

复杂度分析

最坏复杂度:时间复杂度为 O(n^(1/2))

最好复杂度：时间复杂度为 O(n^(1/2))

平均复杂度:时间复杂度为 O(n^(1/2))

实现

思路：采用固定间隔进行跳越，直到找到一个符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置

参考代码如下：

import math
def jumpsearch(sorted_sequence,target):
    n=len(sorted_sequence)
    step=int(math.floor(math.sqrt(n)))
    prev=0
    while sorted_sequence[min(step,n)-1]<target: #按照固定步长跳越
        prev=step
        step=step+int(math.floor(math.sqrt(n)))
        if prev>=n:
            return None
    while sorted_sequence[prev]<target: #线性搜索
        prev=prev+1
        if prev==min(step,n):
            return None
    if sorted_sequence[prev]==target:
        return prev
    else:
        return None
if __name__=='__main__':
    sorted_sequence=[i for i in range(1,10001,2)]
    target=521
    index=jumpsearch(sorted_sequence,target)
    print(index)
快速搜索

快速搜索(quick search),快速选择是一种选择算法，用于查找无序列表中的第 k 个最小元素，它与快速排序算法有关。

快速搜索使用与快速排序相同的整体方法，选择一个元素作为数据透视表，并根据数据透视表将数据分成两部分，因此小于或大于数据透视表。但是，不要像在快速排序中那样递归到双方，而是快速选择仅向一侧递归--与正在搜索的元素的一侧。这将平均复杂度从 O(nlogn) 降低到 o(n)，最坏情况是 O(n^2)。

与快速排序算法一样，快速选择算法通常作为就地算法实现，除了选择第 k 个元素之外，它还对数据进行部分排序。有关与排序的连接的进一步讨论，请参阅快速选择算法。

算法原理

适用性： 用于查找无序列表中的第 k 个最小元素或最大元素

基本思想： 基于二分搜索算法，采用固定间隔进行跳越，直到找到一个符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置。







复杂度分析

最坏复杂度:时间复杂度为 O(n^2)

最好复杂度：时间复杂度为 O(n)

平均复杂度:时间复杂度为 O(n)

实现

思路：和快速排序相同，设置一个对应的分区函数，其作用是对给定元素，对列表执行分为两部分的操作:小于指定元素的部分，大于或等于指定元素的部分。

import random
def partition(sequence,left,right,pivot_index):
    pivot_value=sequence[pivot_index]
    sequence[pivot_index],sequence[right]=sequence[right],sequence[pivot_index] #交换两个元素，使pivot_index与最右边元素置换位置，即先将pivot移动到最右边
    store_index=left
    for i in range(left,right):
        if sequence<pivot_value:
            sequence[store_index],sequence=sequence,sequence[store_index] #交换两个元素，使当前遍历元素(小于pivot_value的元素)与store_index元素置换位置
            store_index=store_index+1 #store_index索引增加1
    sequence[store_index],sequence[right]=sequence[right],sequence[store_index] #交换两个元素，使store_index与最右边元素置换位置，即交换回来pivot最终应该在的位置
    return store_index
def quick_search(sequence,left,right,k):
    if left==right: #如果只有一个元素
        return sequence[left] #返回该元素
    pivot_index=left+random.randint(0,right-left+1) #初始pivot_index，使pivot_index在无序表随机
    pivot_index=partition(sequence,left,right,pivot_index) #pivot在已经排好序的位置
    if k==pivot_index:
        return sequence[k] #返回该位置元素
    elif k<pivot_index:
        return quick_search(sequence,left,pivot_index-1,k) #需要在[left,pivot_index-1]里面继续快速检索
    else:
        return quick_search(sequence,pivot_index+1,right,k) #需要在[pivot_index+1,right]里面继续快速检索
if __name__=='__main__':
    sequence=[12,1,21,34,25,15,35,13,45,100,234,521,345,16,1314]
    left=0
    right=len(sequence)-1
    k=int(input("Find the k'th smallest number in sequence,k="))-1
    value=quick_search(sequence,left,right,k)
    print("The %s 'th smallest number in sequence is : %s"%(k+1,value))
哈希搜索

哈希表就是一种以键-值(key-indexed) 存储数据的结构，只要输入待查找的值即 key，即可查找到其对应的值。哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为 O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

算法原理

适用性： 一个简单无序数组即可实现索引关系即可

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

复杂度分析

最坏复杂度:时间复杂度为 O(1),对于无冲突的哈希表而言

最好复杂度：时间复杂度为 O(1),对于无冲突的哈希表而言

平均复杂度:时间复杂度为 O(1),对于无冲突的哈希表而言

实现

思路：建立哈希表，完成索引结构，即实现哈希搜索的功能。

参考代码如下：

注：本实例代码忽略了数据类型，元素溢出等问题的判断。

class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法
        self.count = size # 最大表长
    def hash(self, key):
        return key % self.count # 散列函数采用除留余数法
    def insert_hash(self, key):
    #插入关键字到哈希表内
        address = self.hash(key) # 求散列地址
        while self.elem[address]: # 当前位置已经有数据了，发生冲突。
            address = (address+1) % self.count # 线性探测下一地址是否可用
        self.elem[address] = key # 没有冲突则直接保存。
    def search_hash(self, key):
    #查找关键字，返回布尔值
        star = address = self.hash(key)
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置
                return False
        return True,address #返回索引值
if __name__ == '__main__':
    list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    hash_table = HashTable(12)
    for i in list_a:
        hash_table.insert_hash(i)
    for i in hash_table.elem:
        if i:
        print((i, hash_table.elem.index(i)), end=" ")
    print("\n")
    print(hash_table.search_hash(15))
    print(hash_table.search_hash(33))
总结

搜索算法是在大量的信息中寻找一个特定的信息元素，在计算机应用中，搜索是常用的基本运算，例如编译程序中符号表的查找。本节内容依次介绍几种常见搜索算法的算法原理和实现过程，以及对应的复杂度分析。回顾下本节内容主要包含了以下内容：

顺序搜索
二分搜索
插值搜索
跳越搜索
快速搜索
哈希搜索
请把文档中所有的示例代码都手动完成并运行对比结果，只有这样才能更加熟练的掌握对应的相关知识。
---------------------
【转载，仅作分享，侵删】
作者：程序员小城
原文：https://blog.csdn.net/w17688977481/article/details/88760071
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-3-25 17:08
奈斯，感谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2