线性搜索（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; //返回中间索引 }
【练手好题】
【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; }
