煮酒与君饮

这个屌丝很懒，什么也没留下！

热门标签

算法笔记（1）—— 搜索算法：线性搜索（LS）、二分搜索（BS）、记忆化搜索（MS）_linear search

作者：煮酒与君饮 | 2024-08-18 19:04:05

踩

linear search

本文章会介绍多种常见的搜索算法，包括线性搜索、二分搜索及记忆化搜索，并用Python语言、C/C++语言实现

线性搜索（LinearSearch）

线性搜索，从字面意思上理解就是按顺序地线性搜索东西，简单点说就是一个一个地去找。在 C/C++ 中判断某个数组里面是否有某元素时，就会用到它。在Python里判断一个元素是否在一个列表中时，可以用 in（成员运算符）运算符（猜测它的原理就是线性搜索）。

【适用情形】搜索序列不是很大的情况

【序列顺序】顺序、乱序均可

【时间复杂度】O(n)

【空间复杂度】O(1)

【动画演示】

**线性搜索（LinearSearch）[动画由Python tkinter模块制作]**

【Python实现】


def LinearSearch(lis: list[int], obj: int): #lis:搜索序列 obj:目标值
    for index, value in enumerate(lis):     #遍历搜索序列
        if value == obj:                    #判断是否为目标值
            return index                    #找到目标值，返回索引
    return None                             #未找到值，返回None

【C/C++实现】


int LinearSearch(int arr[], int length, int obj)		//arr:搜索数组 length:数组长度（或搜索长度） obj:目标值
{
	for(int i = 0; i < length; i++)						//遍历数组
    {
		if(arr[i] == obj)								//判断是否为目标值
			return i;								    //返回索引
	}
	return -1;										    //没有目标值，返回-1
}

【练手好题】

【洛谷】P3383 【模板】线性筛素数

二分搜索（BinarySearch）

二分搜索，也叫二分查找，可以解决线性搜索在搜索时间上的不足。顾名思义，每搜索一次，就二分一次。如果说线性搜索是常数速度，那么二分搜索就是指数速度！

【适用情形】搜索序列单调递增或单调递减（以下实现代码以单调递增为例）

【序列顺序】顺序（顺序增大或顺序减小）

【时间复杂度】O(logn)

【空间复杂度】O(1)

【动画演示】

**二分搜索（BinarySearch）[动画由Python tkinter模块制作]**

【Python实现】

【循环型二分搜索】


def BinarySearch(lis: list[int], obj: int): #lis:搜索序列 obj:目标值
    max_index, min_index = len(lis)-1, 0    #初始化搜索的上下边界（索引）
    while True:                             #无限循环
        middle = (max_index+min_index)//2   #把上下边界（索引）二分，得中间索引
        if max_index < min_index:           #设定循环终止条件（上边界小于下边界，这是不应该出现的情况，所以终止）
            return None                     #循环终止，没有目标值，返回None
        if lis[middle] > obj:               #判断中间值是否大于目标值
            max_index = middle-1            #中间值大于目标值，说明目标值的索引应该在中间索引之下，但不包括中间索引，所以上边界（索引）缩小至中间索引-1
        elif lis[middle] < obj:             #判断中间值是否小于目标值
            min_index = middle+1            #中间值小于目标值，说明目标值的索引应该在中间索引之上，但不包括中间索引，所以下边界（索引）增大至中间索引+1
        else:                               #中间值恰好等于目标值
            return middle                   #返回中间索引

【递归型二分搜索】


##【递归型】二分搜索 ##
def BinarySearch(lis: list[int], obj: int, max_index: int, min_index: int=0):   #lis:搜索序列 obj:目标值 max_index:上索引 min_index:下索引
    middle = (max_index+min_index)//2                                           #把上下边界（索引）二分，得中间索引
    if max_index < min_index:                                                   #设定递归终止条件（上边界小于下边界，这是不应该出现的情况，所以终止）
        return None                                                             #递归终止，没有目标值，返回None
    if lis[middle] > obj:                                                       #判断中间值是否大于目标值
        return BinarySearch(lis, obj, middle-1, min_index)                      #中间值大于目标值，说明目标值的索引应该在中间索引之下，但不包括中间索引，所以上边界（索引）缩小至中间索引-1，递归函数
    elif lis[middle] < obj:                                                     #判断中间值是否小于目标值
        return BinarySearch(lis, obj, max_index, middle+1)                      #中间值小于目标值，说明目标值的索引应该在中间索引之上，但不包括中间索引，所以下边界（索引）增大至中间索引+1，递归函数
    else:                                                                       #中间值恰好等于目标值
        return middle                                                           #返回中间索引

【C/C++实现】

【循环型二分搜索】


int BinarySearch(int arr[], int length, int obj)	    //arr:搜索数组 length:数组长度（或搜索长度） obj:目标值
{
	int max_index = length-1, min_index = 0, middle;	//初始化搜索的上下边界（索引）及中间索引
	while(true)										    //无限循环
	{
		middle = (max_index+min_index)/2;			    //把上下边界（索引）二分，得中间索引
		if(max_index < min_index)					    //设定循环终止条件（上边界小于下边界，这是不应该出现的情况，所以终止）
			return -1;								    //循环终止，没有目标值，返回-1
		if(arr[middle] > obj)						    //判断中间值是否大于目标值
			max_index = middle-1;					    //中间值大于目标值，说明目标值的索引应该在中间索引之下，但不包括中间索引，所以上边界（索引）缩小至中间索引-1
		else if(arr[middle] < obj)					    //判断中间值是否小于目标值
			min_index = middle+1;					    //中间值小于目标值，说明目标值的索引应该在中间索引之上，但不包括中间索引，所以下边界（索引）增大至中间索引+1
		else										    //中间值恰好等于目标值
			return middle;							    //返回中间索引
	}
}

【递归型二分搜索】


int BinarySearch(int arr[], int obj, int max_index, int min_index=0)	//arr:搜索数组 obj:目标值 max_index:上边界（索引） min_index:下边界（索引）
{
	int middle = (max_index+min_index)/2;								//把上下边界（索引）二分，得中间索引
	if(max_index < min_index)											//设定递归终止条件（上边界小于下边界，这是不应该出现的情况，所以终止）
		return -1;														//递归终止，没有目标值，返回-1
	if(arr[middle] > obj)												//判断中间值是否大于目标值
		return BinarySearch(arr, obj, middle-1, min_index);				//中间值大于目标值，说明目标值的索引应该在中间索引之下，但不包括中间索引，所以上边界（索引）缩小至中间索引-1
	else if(arr[middle] < obj)											//判断中间值是否小于目标值
		return BinarySearch(arr, obj, max_index, middle+1);				//中间值小于目标值，说明目标值的索引应该在中间索引之上，但不包括中间索引，所以下边界（索引）增大至中间索引+1
	else																//中间值恰好等于目标值
		return middle;													//返回中间索引
}

【练手好题】

【洛谷】P2249 【深基13.例1】查找

【LeetCode】704. 二分查找

记忆化搜索（MemorySearch）

记忆化搜索，就是在搜索的过程中同时记住一些值（有动态规划的思想），然后在后面要再次用到该值时可以直接进行调用（就避免重复计算了），有点像递推，但递推是直接对数组元素（或者列表元素）进行操作了，是在记录值的同时往后一步一步推导值，每一步之间都有联系，或者说，递推的规律性比较强，而记忆化搜索就比较普适了（个人认为）。记忆化搜索可以解决递归计算速度慢的问题。

【适用情形】搜索过程中会重复计算某值或者重复进行某一过程

【序列顺序】一般事先未知序列

【时间复杂度】不确定，取决于搜索函数（但同问题下，绝对比递归方法小）

【空间复杂度】不确定，取决于搜索函数

【动画演示】

**记忆化搜索（MemorySearch）[动画由Python tkinter模块制作]**

【Python实现】

【记忆化搜索一般操作】


MemLis = [None]*1001                                                      #记忆化列表，用于存储搜索过程中的数据
 
def MS(n):                                                                #定义MS函数，便于读取记忆和存储数据
    if not MemLis[n]:MemLis[n]=MemorySearch(n)                            #如果MemLis[n]的值为None，说明该位置还没有数据被记录，则计算应计算的值并赋值给MemLis[n]
    return MemLis[n]                                                      #返回MemLis[n]的值
 
def MemorySearch(n:int):                                                  #n:第n项
    if <Condition_1>:return <CertainNum>                                  #直接返回数字的情况
    elif <Condition_2>:return MS(<CertainNum_1>)+MS(<CertainNum_2>)+...   #递归调用的情况
    else:...                                                              #其它情况

【Python特有高级操作】


from functools import cache             #引入记忆化搜索装饰器（旧版为lru_cache）
 
@cache                                  #装饰函数
def object_function(*args, **kwargs):   #待装饰的目标函数
    ...
 
'''
装饰完之后的目标函数就是记忆化搜索的函数了，它会在运行的时候申请大量内存来“记忆”
不过该方法不能保证函数递归不超过最大递归深度（1000）
'''

【举个栗子】

现在要我们求斐波那契数列的第500项，读者不妨先用递归试试！再用上面的模板试试！比较一下速度！

记忆化搜索一般解法


MemLis = [None]*1001                            #记忆化列表
 
def MS(n):                                      #定义MS函数，便于读取记忆和存储数据
    if not MemLis[n]:MemLis[n]=MemorySearch(n)  ##如果MemLis[n]的值为None，说明该位置还没有数据被记录，则计算应计算的值并赋值给MemLis[n]
    return MemLis[n]                            #返回MemLis[n]的值
 
def MemorySearch(n:int):                        #n:第n项
    if n==1:return 0                            #斐波那契数列第1项
    elif n==2:return 1                          #斐波那契数列第2项
    else:return MS(n-1)+MS(n-2)                 #斐波那契数列其它项
 
print(MemorySearch(500))                        #输出结果

记忆化装饰器解法


from functools import cache                      #引入装饰器
 
@cache                                           #装饰函数
def fibonacci(n:int):                            #斐波那契函数
    if n == 1:return 0                           #斐波那契数列第1项
    elif n == 2:return 1                         #斐波那契数列第2项
    else:return fibonacci(n-1)+fibonacci(n-2)    #斐波那契数列其它项
 
print(fibonacci(500))                            #输出结果

【C/C++实现】

【记忆化搜索一般操作】


int MemArr[1001];                                                            //用于记忆的数组在内存的要求之下尽可能开大
 
int MS(int n)																 //定义MS函数用于读取记忆和存储数据
{
    int MemorySearch(int n);												 //声明搜索函数
	if(<Condition>)MemArr[n] = MemorySearch(n);								 //如果MemArr[n]的值不满足某种条件，说明MemArr[n]还未存储数据，则计算其应有的值并赋值给MemArr[n]
	return MemArr[n];														 //返回MemArr[n]的值
}
 
int MemorySearch(int n)                                                      //n:第n项
{
	if(<Condition_1>)return <CertainNum>;                                    //直接返回数字的情况
	else if(<Condition_2>)return MS(<CertainNum_1>)+MS(<CertainNum_2>)+...;  //递归调用的情况
	else ...;                                                                //其他类似的情况
}

【C/C++特有高级操作】


#define MS(n) (<Condition>?MemArr[n]:MemArr[n]=MemorySearch(n))              //记忆化的宏函数，使代码结构简单清晰
 
int MemArr[1001];                                                            //用于记忆的数组在内存的要求之下尽可能开大
 
int MemorySearch(int n)                                                      //n:第n项
{
	if(<Condition_1>)return <CertainNum>;                                    //直接返回数字的情况
	else if(<Condition_2>)return MS(<CertainNum_1>)+MS(<CertainNum_2>)+...;  //递归调用的情况
	else ...;                                                                //其他类似的情况
}

【举个栗子】

现在要我们求斐波那契数列的第20项，读者不妨先用递归试试！再用上面的记忆化搜索的模板试试！

记忆化搜索一般解法


#include <iostream>
using namespace std;
int MemArr[1000];								//记忆数组
 
int MS(int n)									//定义MS函数用于读取记忆和存储数据
{
	int MemorySearch(int n);					//声明搜索函数
	if(!MemArr[n])MemArr[n] = MemorySearch(n);	//如果MemArr[n]的值不满足条件，说明MemArr[n]还未存储数据，则计算其应有的值并赋值给MemArr[n]
	return MemArr[n];							//返回MemArr[n]的值
}
 
int MemorySearch(int n)							//n:第n项
{
	if(n==1)return 0;							//斐波那契数列第1项
	else if(n==2)return 1;						//斐波那契数列第2项
	else return MS(n-1)+MS(n-2);				//斐波那契数列其他项
}
 
int main(){
	cout<<MemorySearch(20);						//输出斐波那契数列第20项
	return 0;
}

记忆化宏函数解法


#include <iostream>
#define MS(n) (MemArr[n]?MemArr[n]:MemArr[n]=MemorySearch(n))    //记忆化的宏函数
using namespace std;
 
int MemArr[1001];                                                //记忆数组
 
int MemorySearch(int n)                                          //n:第n项
{
	if(n==1)return 0;                                            //斐波那契数列第1项
	else if(n==2)return 1;                                       //斐波那契数列第2项
	else return MS(n-1)+MS(n-2);                                 //斐波那契数列其它项
}
 
int main()
{
	cout<<MemorySearch(20);                                      //输出斐波那契数列第20项
	return 0;
}

【练手好题】

【洛谷】P1464 Function

【都看到这里了，点个赞再走吧！】

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】