Ste*_*314 23
二次搜索有两个原因,每次迭代一次比较.性能越不重要.检测早期使用每次迭代的两个比较精确匹配保存循环的平均一次迭代,而(假设比较涉及显著作品)二分查找每个迭代一个比较几乎减半每次迭代完成的工作.
二进制搜索整数数组,它可能无论如何都没有什么区别.即使进行相当昂贵的比较,渐近性能也是相同的,在大多数情况下,半可能不值得追求.此外,昂贵的比较通常被编码为返回负数,零或正数的函数<,==或者>,因此,无论如何,您可以以相当于一个价格的价格进行两次比较.
使用每次迭代进行一次比较进行二进制搜索的重要原因是因为您可以获得比仅仅相等匹配更有用的结果.你可以做的主要搜索是......
这些都减少到相同的基本算法.很好地理解这一点,你可以很容易地编码所有的变种并不困难,但我没有真正看到一个很好的解释 - 只有伪代码和数学证明.这是我尝试解释的.
有些游戏的目的是让目标尽可能接近目标而不会超调.将其更改为"underhooting",这就是"Find First>"的作用.在搜索期间的某个阶段考虑范围...
| lower bound | goal | upper bound
+-----------------+-------------------------+--------------
| Illegal | better worse |
+-----------------+-------------------------+--------------
仍然需要搜索当前上限和下限之间的范围.我们的目标是(通常)在某处,但我们还不知道在哪里.关于上限之上的项目的有趣观点是,它们是合法的,因为它们大于目标.我们可以说当前上限之上的项目是我们迄今为止最好的解决方案.我们甚至可以说,这在一开始,虽然有可能是在该位置没有项目 - 从某种意义上说,如果没有有效的在范围内的解决方案,还没有被推翻最好的解决办法是刚刚过去的上界.
在每次迭代中,我们选择一个项目来比较上限和下限.对于二进制搜索,这是一个圆形的中途项目.对于二叉树搜索,它由树的结构决定.原则是相同的.
当我们搜索的项目大于我们的目标时,我们会使用比较测试项目Item [testpos] > goal.如果结果是错误的,我们会超出(或低于)我们的目标,因此我们保留现有的最佳解决方案,并向上调整我们的下限.如果结果为真,我们找到了一个新的最佳解决方案,所以我们调整上限来反映这一点.
无论哪种方式,我们都不想再次比较该测试项目,因此我们调整我们的界限以消除(仅仅)测试项目从搜索范围.粗心大意通常导致无限循环.
通常,使用半开范围 - 包含下限和独占上限.使用此系统,上限索引处的项目不在搜索范围内(至少现在不是),但它是迄今为止最好的解决方案.向下移动下限时,将其移动到testpos+1(以从范围中排除刚刚测试的项目).当您向上移动上限时,将其移动到testpos(无论如何,上限都是独占的).
if (item[testpos] > goal)
{
// new best-so-far
upperbound = testpos;
}
else
{
lowerbound = testpos + 1;
}
当下限和上限之间的范围为空时(使用半开,当两者具有相同的索引时),您的结果是您最近的最佳解决方案,恰好高于您的上限(即在上限索引处)半开).
所以完整的算法是......
while (upperbound > lowerbound)
{
testpos = lowerbound + ((upperbound-lowerbound) / 2);
if (item[testpos] > goal)
{
// new best-so-far
upperbound = testpos;
}
else
{
lowerbound = testpos + 1;
}
}
要更改first key > goal为first key >= goal,您可以if在行中切换比较运算符.相对运算符和目标可以由单个参数替换 - 谓词函数,如果(并且仅当)其参数位于目标的大于一侧时返回true.
这给你"first>"和"first> =".要获得"first ==",请使用"first> ="并在循环退出后添加相等性检查.
对于"last <"等,原理与上述相同,但反映了范围.这只是意味着您交换绑定调整(但不是注释)以及更改运算符.但在此之前,请考虑以下事项......
a > b == !(a <= b)
a >= b == !(a < b)
也...
当我们在搜索过程中移动边界时,双方都会朝着目标移动,直到他们在目标处相遇.并且在下限下方有一个特殊项目,正如上限正好在上方...
while (upperbound > lowerbound)
{
testpos = lowerbound + ((upperbound-lowerbound) / 2);
if (item[testpos] > goal)
{
// new best-so-far for first key > goal at [upperbound]
upperbound = testpos;
}
else
{
// new best-so-far for last key <= goal at [lowerbound - 1]
lowerbound = testpos + 1;
}
}
所以在某种程度上,我们有两个互补的搜索一次运行.当上限和下限相遇时,我们在该单边界的每一侧都有一个有用的搜索结果.
对于所有情况,原始的"想象的"越界最好的位置是你的最终结果(搜索范围内没有匹配).在==对第一个==和最后一个==情况进行最终检查之前,需要检查这一点.它也可能是有用的行为 - 例如,如果您正在搜索插入目标项的位置,如果所有现有项都小于您的目标项,则在现有项结束后添加它是正确的做法.
关于选择测试点的几点注意事项......
testpos = lowerbound + ((upperbound-lowerbound) / 2);
首先,这不会溢出,不像更明显((lowerbound +
upperbound)/2).它也适用于指针和整数索引.
其次,假设该部门向下舍入.对于非负数进行舍入是可以的(所有你可以在C中确定)因为差异总是非负的.
如果您使用非半开范围,这是一个可能需要注意的方面 - 确保测试位置在搜索范围内,而不仅仅是在外(在已经找到的最佳位置之一上) .
最后,在二叉树搜索中,边界的移动是隐式的,并且选择testpos是内置在树的结构中(可能是不平衡的),但是相同的原则适用于搜索正在进行的操作.在这种情况下,我们选择子节点来缩小隐式范围.对于第一场比赛的情况下,无论是我们已经找到了一个新的更小的最佳匹配(去下子找到的希望更小,更好的一个),或者我们已经打捞(转到更高孩子恢复的希望).同样,可以通过切换比较运算符来处理四种主要情况.
顺便说一句 - 有更多可能的运算符用于该模板参数.考虑按年和月分类的数组.也许你想找到特定年份的第一个项目.为此,编写一个比较年份并忽略月份的比较函数 - 如果年份相等,则目标值相等,但目标值可能与甚至没有月份值的键的类型不同相比.我认为这是一个"部分密钥比较",并将其插入到您的二进制搜索模板中,您将得到我认为的"部分密钥搜索".
编辑 下面的段落曾经说过"1999年12月31日等于2000年2月1日".除非中间的整个范围也被认为是平等的,否则这将无效.关键是开始日期和结束日期的所有三个部分都不同,所以你不处理"部分"键,但是被认为与搜索等效的键必须在容器中形成一个连续的块,这通常意味着有序的可能键集合中的连续块.
它也不仅仅是"部分"键.您的自定义比较可能会将1999年12月31日视为等于2000年1月1日,但所有其他日期都不同.关键是自定义比较必须与关于排序的原始关键一致,但是考虑所有不同的值可能不那么挑剔 - 它可以将一系列键视为"等价类".
关于我之前应该包含的界限的额外说明,但我当时可能没有这样想过.
考虑边界的一种方式是它们根本不是项目索引.边界是两个项目之间的边界线,因此您可以像对项目编号一样轻松地对边界线进行编号...
| | | | | | | | |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| | | | | | | | |
0 1 2 3 4 5 6 7 8
显然,边界的编号与项目的编号有关.只要您从左到右对数字进行编号,并且对项目进行编号的方式相同(在这种情况下从零开始),结果实际上与常见的半开公约相同.
有可能选择一个中间界限将范围精确地分成两部分,但这不是二元搜索的作用.对于二进制搜索,您选择要测试的项目 - 而不是绑定.该项目将在此迭代中进行测试,绝不能再次测试,因此它将从两个子范围中排除.
| | | | | | | | |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| | | | | | | | |
0 1 2 3 4 5 6 7 8
^
|<-------------------|------------->|
|
|<--------------->| | |<--------->|
low range i hi range
因此算法testpos和testpos+1算法是将项索引转换为绑定索引的两种情况.当然,如果两个边界相等,则该范围内没有项目可供选择,因此循环无法继续,唯一可能的结果是一个边界值.
上面显示的范围只是仍在搜索的范围 - 我们打算在证明较低和证明较高的范围之间关闭的差距.
在这个模型中,二元搜索正在搜索两种有序值之间的边界 - 那些被归类为"较低"的那些和被归类为"较高"的那些.谓词测试对一个项目进行分类.没有"相等"类 - 等于键值是较高类(for x[i] >= key)或较低类(for x[i] > key)的一部分.