python条件查询或in_搜索算法inPython
介绍
本节内容将介绍⼏种常见的搜索算法(主要包含顺序搜索，⼆分搜索，插值搜索，跳越搜索，快速搜索，哈希搜索)的算法原理，算法复杂度的分析，以及如何实现。
知识点顺序搜索
⼆分搜索
插值搜索
跳越搜索
快速搜索
哈希搜索
搜索算法
搜索算法是利⽤计算机的⾼性能来有⽬的的穷举⼀个问题解空间的部分或所有的可能情况，从⽽求出问题的解的⼀种⽅法。
注：定义来⾃百度百科。
在学习算法的时候，需要学会理解算法是如何实现的，掌握其算法的原理，以及如何判断算法的优越性。
我们将在接下来的内容，逐步理解这些简单的搜索算法。
补充概念
算法复杂度：指算法在编写成可执⾏程序后，运⾏时所需要的资源，资源包括时间资源和内存资源。时间资源⽤时间复杂度表⽰，空间资源⽤空间复杂度表⽰。
时间复杂度：抛开与计算机硬件、软件有关的因素，⼀个程序的运⾏时间依赖于算法的好坏和问题的输⼊规模。语句总的执⾏次数 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[i]:
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
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
right=Third1-1
快速排序python实现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
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]
prev=step
step=step+int(math.floor(math.sqrt(n)))
if prev>=n:
return None
while sorted_sequence[prev]
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)
快速搜索

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。