algorithm - 如何更好地理解“每次比较一次”的二进制搜索？

Question

每次比较一次二进制搜索的意义是什么？您能解释一下它是如何工作的吗？

Answer 1

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

二进制搜索整数数组，可能没有什么区别
无论哪种方式。即使比较昂贵，渐近地
性能是相同的，并且一半多于负一可能不值得
在大多数情况下追求。此外，昂贵的比较通常被编码为对<，==或>返回负，零或正数的函数，因此无论如何您都可以以一个价格获得这两个比较。

对每个迭代进行一次比较的二进制搜索的重要原因是
因为您可以获得比同等匹配更有用的结果。主要的
您可以做的搜索是...


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


这些都归结为相同的基本算法。足够了解这一点
您可以轻松编写所有变体的代码并不难，但我没有
确实看到了一个很好的解释-仅伪代码和数学证明。这个
是我的一种解释尝试。

在某些游戏中，想法是尽可能接近目标
没有超调。将其更改为“ undershooting”，这就是“ Find
首先>”。在搜索过程中的某个阶段考虑范围...

| 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)

也...


位置（最后一个关键<目标）=位置（一个关键> =目标）-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 = 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）的一部分。