如何更好地理解每比较一次比较二进制搜索？

Question

单比较每迭代二进制搜索的要点是什么？你能解释它是如何工作的吗？

Answer 1

二元搜索有两个原因，每次迭代一次比较。性能不太重要的是 。提前检测完全匹配，每次迭代使用两个 比较节省循环的平均一次迭代，而 （假设比较涉及重要工作），每次迭代比较一次 ，几乎减半了每次迭代完成的工作。

二进制搜索一个整数数组，它可能无论如何没有什么区别 。即使是相当昂贵的比较，渐近地表现也是一样的，在大多数情况下，可能不会有价值追求的是一半而不是一个负值。此外，昂贵的比较常常被编码为返回负数，零或正的<,==或>的函数，因此无论如何你都可以得到两者的比较。

每次迭代比较一次进行二分搜索的重要原因是 ，因为您可以获得比仅仅一些等号匹配更有用的结果。主要 搜索你可以做的是...

• 一键>目标
• 一键> =目标
• 一键==目标
• 最后关键<目标
• 最后关键< =目标
• 最后一个关键==目标

这些都减少到相同的基本算法。理解这个足够好的 ，你可以很容易地编写所有的变体并不困难，但我没有真正看到一个很好的解释 - 只有伪代码和数学证明。这是我试图解释的 。

有一些游戏的想法是尽可能接近目标 没有超调。将其改为“下冲”，这就是“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> =”，并在循环退出后添加相等性检查。

对于“last <”等，其原理与上述相同，但范围为 反映。这只是意味着你调整了边界调整（但不包括 评论）以及更改运算符。但在此之前，请考虑以下内容...

a > b == !(a <= b) 
a >= b == !(a < b) 

另外...

• 位置（最后的键<目标）=位置（第一密钥> =目标） - 1个
• 位置（最后的键< =目标）=位置（第一密钥>目标） - 1

当我们在搜索过程中移动我们的界限时，双方都会朝目标移动，直到他们相遇。还有刚刚低于下限特殊的项目，就像有只超过上限时...

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的选择笔记...

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是翻译项目索引，约束指数的两种情况。当然，如果两个边界相等，则该范围内没有项目可供选择，因此循环无法继续，唯一可能的结果就是该边界值。

上面显示的范围只是仍然需要搜索的范围 - 我们打算在久经考验的和已证明的更高范围之间关闭的差距。

在此模型中，二分查找搜索两个有序种类值之间的边界 - 分类为“较低”和归类为“较高”的那些边界。谓词测试将一个项目分类。没有“平等”等级 - 等于键值是较高等级（对于x[i] >= key）或较低等级（对于x[i] > key）的一部分。