搜索匹配算法

‘壹’ 双目视觉的匹配算法是不是有好几种具体是哪几种

与普通的图像模板匹配不同的是，立体匹配是通过在两幅或多幅存在视点差异、几何畸变、灰度畸变、噪声干扰的图像对之间进行的，不存在任何标准模板进行匹配。立体匹配方法一般包含以下三个问题:(1)基元的选择，即选择适当的图像特征如点、直线、相位等作为匹配基元;(2)匹配的准则，将关于物理世界的某些固有特征表示为匹配所必须遵循的若干规则，使匹配结果能真实反映景物的本来面目;(3)算法结构，通过利用适当的数学方法设计能正确匹配所选择基元的稳定算法。

根据匹配基元的不同，立体视觉匹配算法目前主要分为三大类,即区域匹配、相位匹配和特征匹配:

基于区域灰度的匹配算法是把一幅图像(基准图)中某一点的灰度邻域作为模板，在另一幅图像(待匹配图)中搜索具有相同(或相似)灰度值分布的对应点邻域，从而实现两幅图像的匹配。这类算法的性能取决于度量算法及搜索策略的选择。另外，也必须考虑匹配窗口大小、形式的选择，大窗口对于景物中存在的遮挡或图像不光滑的情况会更多的出现误匹配，小窗口则不具有足够的灰度变化信息，不同的窗口形式对匹配信息也会有不同的影响。因此应该合理选取匹配区域的大小和形式来达到较好的匹配结果。

相位匹配是近二十年发展起来的一种匹配算法，相位作为匹配基元，即认为图像对中的对应点局部相位是一致的。最常用的相位匹配算法有相位相关法和相位差——频率法，虽然该方法是一种性能稳定、具有较强的抗辐射抗透视畸变能力、简单高效、能得到稠密视差图的特征匹配方法。但是，当局部结构存在的假设不成立时，相位匹配算法因带通输出信号的幅度太低而失去有效性，也就是通常提到的相位奇点问题，在相位奇点附近，相位信息对位置和频率的变化极为敏感，因此用这些像素所确定的相位差异来衡量匹配误差将导致极不可靠的结果。此外，相位匹配算法的收敛范围与带通滤波器的波长有关，通常要考虑相位卷绕，在用相位差进行视差计算时，由于所采用的相位只是原信号某一带通条件下的相位，故视差估计只能限制在某一限定范围之内，随视差范围的增大，其精确性会有所下降。

基于特征的图像匹配方法是目前最常用的方法之一，由于它能够将对整个图像进行的各种分析转化为对图像特征(特征点、特征曲线等)的分析的优点，从而大大减小了图像处理过程的计算量，对灰度变化、图像变形、噪音污染以及景物遮挡等都有较好的适应能力。

基于特征的匹配方法是为使匹配过程满足一定的抗噪能力且减少歧义性问题而提出来的。与基于区域的匹配方法不同，基于特征的匹配方法是有选择地匹配能表示景物自身特性的特征，通过更多地强调空间景物的结构信息来解决匹配歧义性问题。这类方法将匹配的搜索范围限制在一系列稀疏的特征上。利用特征间的距离作为度量手段，具有最小距离的特征对就是最相近的特征对，也就是匹配对。特征间的距离度量有最大最小距离、欧氏距离等。

特征点匹配算法严格意义上可以分成特征提取、特征匹配和消除不良匹配点三步。特征匹配不直接依赖于灰度，具有较强的抗干扰性。该类方法首先从待匹配的图像中提取特征，用相似性度量和一些约束条件确定几何变换，最后将该变换作用于待匹配图像。匹配中常用的特征基元有角点、边缘、轮廓、直线、颜色、纹理等。同时，特征匹配算法也同样地存在着一些不足，主要表现为:

(l)特征在图像中的稀疏性决定了特征匹配只能得到稀疏的视差场，要获得密集的视差场必须通过使用插值的过程，插值过程通常较为复杂。

(2)特征的提取和定位的准确与否直接影响特征匹配结果的精确度。

(3)由于其应用场合的局限性，特征匹配往往适用于具有特征信息显着的环境中，在缺少显着主导特征环境中该方法有很大困难。

总之，特征匹配基元包含了算法编程上的灵活性以及令人满意的统计特性。算法的许多约束条件均能清楚地应用于数据结构，而数据结构的规则性使得特征匹配非常适用于硬件设计。例如，基于线段的特征匹配算法将场景模型描绘成相互联结的边缘线段，而不是区域匹配中的平面模型，因此能很好地处理一些几何畸变问题，对对比度和明显的光照变化等相对稳定。特征匹配由于不直接依赖于灰度，计算量小，比基于区域的匹配算法速度快的多。且由于边缘特征往往出现在视差不连续的区域，特征匹配较易处理立体视觉匹配中的视差不连续问题。

‘贰’ 全文检索算法，请问谁能给我点头绪落，不懂啊。。

全文检索技术
全文检索是指索引程序扫描文章中的每个词并建立对应索引，记录该词出现的位置和次数。当通过搜索引擎查询时，检索程序就在记录的索引进行查找并返回给用户。全文检索又分为基于字的全文索引和基于词的全文索引。基于字的全文索引会对内容中的每个字建立索引并记录，此方法查全率高，但查准率低，特别是对于中文，有时搜索马克，会列出马克思的结果。基于词的全文索引是把一个词语作为一个单位进行索引记录，并能处理同义词。搜索引擎有自己的词库，当用户搜索时，搜索引擎会从词库中抽取关键词作为索引项，这样可以大大提高检索的准确率。
中文分词技术
一直以来大家都比较熟悉网络，网络有自己的中文分词技术。一般采用的包括正向最大匹配，反向最大匹配，最佳匹配法，专家系统方法等。其中最大正向匹配是最常用的分词解决方案，它采用机械式算法，通过建立词典并进行正向最大匹配对中文进行分词。举个简单的例子比如搜索“北京大学在哪里”，则返回结果很多都是包含北京大学，北大等词语的网页，搜索引擎就是采用正向最大匹配去判断，把北京大学当做一个词语来索引记录并返回。当然，正向最大匹配也有不完整性，比如长度过长的词语，搜索引擎有时无法准确的分词，或者对前后都相互关联的词无法准确分词。例如“结合成分子时”，会被返回结合、成分、子时，而有时我们想要的关键词是“分子”。
很多时候网络都会根据自己词库中词语的权重进行拆分，权重的计算基于生活各个方面，比较复杂，搜索引擎要做的就是返回用户最想要的结果，有时站长们做网站要站在用户的角度去考虑问题，其实这也是站在搜索引擎的角度考虑问题，不论在确定目标关键词或者是长尾关键词时，都可以根据中文分词的原理来选择，这样可以最大化的减少无用功。
分词原理不断在变化，不断在更新，我们应该继续学习，只有掌握了本质才能抓住实质。

‘叁’ 运动估计的搜索算法

匹配误差函数，可以用各种优化方法进行最小化，这就需要我们开发出高效的运动搜索算法，
主要的几种算法归纳如下： 为当前帧的一个给定块确定最优位移矢量的全局搜索算法方法是：在一个预先定义的搜索区域
内，把它与参考帧中所有的候选块进行比较，并且寻找具有最小匹配误差的一个。这两个块之间的
位移就是所估计的 MV，这样做带来的结果必然导致极大的计算量。
选择搜索区域一般是关于当前块对称的，左边和右边各有 Rx 个像素，上边和下边各有 Ry个像素。
如果已知在水平和垂直方向运动的动态范围是相同的，那么 Rx=Ry=R。估计的精度是由搜索的步长决定的，步长是相邻两个候选块在水平或者垂直方向上的距离。通常，沿着两个方向使用相同的步长。在最简单的情况下，步长是一个像素，称为整数像素精度搜索，该种算法也称为无损搜索算法。 由于在穷尽块匹配算法中搜索相应块的步长不一定是整数，一般来说，为了实现 1/K像素步长，对参考帧必须进行 K倍内插。根据实验证明，与整像素精度搜索相比，半像素精度搜索在估计精度上有很大提高，特别是对于低清晰度视频。
但是，应用分数像素步长，搜索算法的复杂性大大增加，例如，使用半像素搜索，搜索点的总数比整数像素精度搜索大四倍以上。
那么，如何确定适合运动估计的搜索步长，对于视频编码的帧间编码来说，即使得预测误差最小化。 快速搜索算法和全局搜索算法相比，虽然只能得到次最佳的匹配结果，但在减少运算量方面效果显着。
1） 二维对数搜索法
这种算法的基本思路是采用大菱形搜索模式和小菱形搜索模式，步骤如图 6.4.20 所示，从相应于零位移的位置开始搜索，每一步试验菱形排列的五个搜索点。下一步，把中心移到前一步找到的最佳匹配点并重复菱形搜索。当最佳匹配点是中心点或是在最大搜索区域的边界上时，就减小搜索步长（菱形的半径） 。否则步长保持不变。当步长减小到一个像素时就到达了最后一步，并且在这最
后一步检验九个搜索点。初始搜索步长一般设为最大搜索区域的一半。
其后这类算法在搜索模式上又做了比较多的改进，在搜索模式上采用了矩形模式，还有六边形模式、十字形模式等等。
2） 三步搜索法
这种搜索的步长从等于或者略大于最大搜索范围的一半开始。第一步，在起始点和周围八个 “1”标出的点上计算匹配误差，如果最小匹配误差在起始点出现，则认为没有运动；第二步，以第一步中匹配误差最小的点（图中起始点箭头指向的“1”）为中心，计算以“2”标出的 8个点处的匹配误差。注意，在每一步中搜索步长搜都比上一步长减少一半，以得到更准确的估计；在第三步以后就能得到最终的估计结果，这时从搜索点到中心点的距离为一个像素。
但是，上述一些快速算法更适合用于估计运动幅度比较大的场合，对于部分运动幅度小的场合，它们容易落入局部最小值而导致匹配精度很差，已经有很多各种各样的视频流证明了这一点。
现在，针对这一缺点，国内外诸多专家学者也提出了相应的应对措施，特别是针对H.264编码标准要求的一些快速算法的改进，并取得卓越的效果。例如[7]中提到的基于全局最小值具有自适应性的快速算法，这种算法通过在每一搜索步骤选择多个搜索结果，基于这些搜索结果之间的匹配误差的不同得到的最佳搜索点，因而可以很好地解决落入局部最小值的问题。
[8]中提到一种适用于H．264的基于自适应搜索范围的快速运动估计算法，经过实验证明对于如salesman等中小运动序列，其速度可接近全局搜索算法的400倍，接近三步搜索算法的4倍；而对于大运动序列，如table tennis，该算法则会自动调节搜索点数以适应复杂的运动。当从总体上考察速度方面的性能时，可以看到，该算法平均速度是全局搜索算法的287．4倍，三步搜索的2．8倍。 分级搜索算法的基本思想是从最低分辨率开始逐级精度的进行不断优化的运动搜索策略，首先取得两个原始图象帧的金子塔表示，从上到下分辨率逐级变细，从顶端开始，选择一个尺寸比较大的数据块进行一个比较粗略的运动搜索过程，对在此基础上进行亚抽样（即通过降低数据块尺寸（或提高抽样分辨率）和减少搜索范围的办法）进行到下一个较细的级来细化运动矢量，而一个新的搜索过程可以在上一级搜索到的最优运动矢量周围进行。在亚抽样的过程中也有着不同的抽样方式和抽样滤波器。这种方法的优点是运算量的下降比例比较大，而且搜索的比较全面。
缺点是由于亚抽样或者滤波器的采用而使内存的需求增加，另外如果场景细节过多可能会容易落入局部最小点。 由于物体的运动千变万化，很难用一种简单的模型去描述，也很难用一种单一的算法来搜索最佳运动矢量，因此实际上大多采用多种搜索算法相组合的办法，可以在很大程度上提高预测的有效性和鲁棒性。
事实上，在运动估计时也并不是单一使用上述某一类搜索算法，而是根据各类算法的优点灵活组合采纳。在运动幅度比较大的情况下可以采用自适应的菱形搜索法和六边形搜索法，这样可以大大节省码率而图象质量并未有所下降。在运动图象非常复杂的情况下，采用全局搜索法在比特数相对来说增加不多的情况下使得图象质量得到保证。 H.264 编码标准草案推荐使用 1/4分数像素精度搜索。[6]中提到在整像素搜索时采用非对称十字型多层次六边形格点运动搜索算法，然后采用钻石搜索模型来进行分数像素精度运动估计。
解码器要求传送的比特数最小化，而复杂的模型需要更多的比特数来传输运动矢量，而且易受噪声影响。因此，在提高视频的编码效率的技术中，运动补偿精度的提高和比特数最小化是相互矛盾的，这就需要我们在运动估计的准确性和表示运动所用的比特数之间作出折中的选择。它的效果与选用的运动模型是密切相关的。

‘肆’ 【算法笔记】字符串匹配

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：

主串和模式串：
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m

我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法的时间复杂度是 O(n*m)

等价于

比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。

看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰
内容来自 http://www.ruanyifeng.com/blog/

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

因为 6 - 2 等于4，所以将搜索词向后移动4位。

因为空格与C不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

因为空格与A不匹配，继续后移一位。

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是着名的KMP 算法的 3 到 4 倍。

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）

未完待续

参考文章：
字符串匹配的Boyer-Moore算法

‘伍’ 字符串匹配的传统算法

传统的匹配算法
串匹配算法虽然发展了几十年，然而非常实用的算法是近年才出现。串匹配问题的研究存在理论研究和实际应用的脱节。那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。而开发人员只追求实际应用中尽可能快的算法。两者之间从不注意对方在干什么。将理论研究和实际应用结合的算法(如BNDM算法)只是近年才出现。在实际应用中常常很难找到适合需求的算法——这样的算法实际上是存在的，但是只有资深专家才比较了解。考虑如下情况，一位软件开发人员，或者一位计算生物学家，或者一位研究人员，又或者一位学生，对字符串匹配领域并没有深入了解，可是现在需要处理一个文本搜索问题。那些汗牛充栋的书籍使得阅读者淹没在各种匹配算法的海洋中，却没有足够的知识选择最适用的算法。最后，常常导致这样的局面：选择一种最简单的算法加以实现。这往往导致很差的性能，从而影响整个开发系统的质量。更糟糕的是，选择了一个理论上看起来很漂亮的算法，并且花费了大量精力去实现。结果，却发现实际效果和一个简单算法差不多，甚至还不如简单算法。因此，应该选用一种“实用”算法，即在实际应用中性能较好，并且一个普通程序员能在几小时内完成算法的实现代码。另外，在字符串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。
传统的串匹配算法可以概括为前缀搜索、后缀搜索、子串搜索。代表算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技术包括滑动窗口、位并行、自动机、后缀树等。

‘陆’ 数据结构有哪些基本算法

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

可以理解为：程序设计 = 数据结构 + 算法

数据结构算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。

1、输入：一个算法具有零个或者多个输出。以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。后面一句话翻译过来就是，如果一个算法本身给出了初始条件，那么可以没有输出。比如，打印一句话：NSLog(@"你最牛逼！");

2、输出：算法至少有一个输出。也就是说，算法一定要有输出。输出的形式可以是打印，也可以使返回一个值或者多个值等。也可以是显示某些提示。

3、有穷性：算法的执行步骤是有限的，算法的执行时间也是有限的。

4、确定性：算法的每个步骤都有确定的含义，不会出现二义性。

5、可行性：算法是可用的，也就是能够解决当前问题。

数据结果的基本算法有：

1、图搜索（广度优先、深度优先）深度优先特别重要

2、排序

3、动态规划

4、匹配算法和网络流算法

5、正则表达式和字符串匹配

6、三路划分-快速排序

7、合并排序（更具扩展性，复杂度类似快速排序）

8、DF/BF 搜索 （要知道使用场景）

9、Prim / Kruskal （最小生成树）

10、Dijkstra （最短路径算法）

11、选择算法

‘柒’ 算法是什么急!!!!

算法 Algorithm

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

1、有穷性： 一个算法必须保证执行有限步之后结束；

2、确切性： 算法的每一步骤必须有确切的定义；

3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性： 算法原则上能纤脊够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

算法的设计要求
1）正确性（Correctness）
有4个层次：
A．程序不含语法错误；
B．程序对几组输入数据能够得出满足规格要求的结果；
C．程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果；
D．程序对一切合法的输入数据都能产生满足规格要求的结果。
2）可读性（Readability）
算法的第一目的是为了阅读和交流；
可读性有助于对算法的理解；
可读性有助于对算法的调试和修改。
3）高效率与低存储量
处理速度快；存储容量小
时困棚间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。
算法的描述 算法的描述方式（常用的）
算法描述 自然语言
流程图 特定的表示算法的图形符号
伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言
类语言 类似高级语言的语言，例如，类PASCAL、类C语言。

算法的评价 算法评价的标准：时毁尺渗间复杂度和空间复杂度。
1）时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。
常见的时间复杂度有： O（1）常数阶；O（logn）对数阶；O（n）线性阶；O（n＾2）平方阶
2）空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。

时间复杂度举例
（a） X：=X+1 ； O（1）
（b） FOR I：=1 TO n DO
X：= X+1； O（n）
（c） FOR I：= 1 TO n DO
FOR J：= 1 TO n DO
X：= X+1； O（n＾2）

“算法”一词最早来自公元 9世纪 波斯数学家比阿勒·霍瓦里松的一本影响深远的着作《代数对话录》。20世纪的 英国 数学家 图灵 提出了着名的图灵论点，并抽象出了一台机器，这台机器被我们称之为 图灵机 。图灵的思想对算法的发展起到了重要的作用。
算法是 计算机 处理信息的本质，因为 计算机程序 本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，数据会从输入设备读取，写入输出设备，可能保存起来以供以后使用。
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小 可以将下面的算法形象地称为“捡豆子”：
首先将第一颗豆子（数列中的第一个数字）放入口袋中。
从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先的豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法，用近似于 编程语言 的 伪代码 表示
给定：一个数列“list"，以及数列的长度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest
符号说明:
= 用于表示赋值。即：右边的值被赋予给左边的变量。
List[counter] 用于表示数列中的第 counter 项。例如：如果 counter 的值是5，那么 List[counter] 表示数列中的第5项。
<= 用于表示“小于或等于”。
算法的分类
（一）基本算法 :
1.枚举
2.搜索:
深度优先搜索
广度优先搜索
启发式搜索
遗传算法
（二）数据结构的算法
（三）数论与代数算法
（四）计算几何的算法：求凸包
（五）图论 算法：
1.哈夫曼编码
2.树的遍历
3.最短路径 算法
4.最小生成树 算法
5.最小树形图
6.网络流 算法
7.匹配算法
（六）动态规划
（七）其他：
1.数值分析
2.加密算法
3.排序 算法
4.检索算法
5.随机化算法

‘捌’ 二分搜索算法是利用什么实现的算法

二分搜索算法是利用排除剩余元素中一半的元素实现的算法。

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索算法原理：

1、如果待查序列为空，那么就返回－1，并退出算法；这表示查找不到目标元素。如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。如果不相等，就再比较这两个元素的大小。

2、如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

3、如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。

‘玖’ 三步搜索法总是能得到最优的预测块吗

不能总是得到衡仔晌。根咐锋据查询相关公开信息显示，TSS最初由ToshioKOGA在1981年提出，用于最初计算机性能问题，以及计算复杂度的问题，所以设计是搜索为±7范围内，并不能总是戚帆得到最优的预测块，而这个搜索差不多三步计算即可，三步搜索法由此而生。三步搜索法是一种非常经典的快速运动估计块匹配算法。