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

二进制搜索整数数组，两种方式都可能没有什么区别。即使进行了相当昂贵的比较，渐近地，性能仍然是相同的，并且在大多数情况下不值得追求负一半而不是负一半。此外，昂贵的比较往往是编码为函数返回负数，零或正的<，==或者>，这样你就可以得到两个比较，一个漂亮多大的代价呢。

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

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

这些都归结为相同的基本算法。充分理解这一点以使您可以轻松地编码所有变体并不难，但是我并没有真正看到很好的解释-仅是伪代码和数学证明。这是我尝试的一种解释。

在某些游戏中，其想法是尽可能地接近目标而又不过分。将其更改为“ undershooting”，这就是“ 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)

也…

• 位置（最后一个关键<目标）=位置（一个关键> =目标）-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是将项目索引转换为绑定索引的两种情况。当然，如果两个边界相等，则该范围内没有项目可供选择，因此循环无法继续，唯一可能的结果是一个边界值。

上面显示的范围只是仍要搜索的范围-我们打算缩小已证明的较低范围和已证明的较高范围之间的差距。

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