1.5是Ruby中0到无穷大之间的中点

0和无穷大之间的中点是多少？嗯，答案是不同的，具体取决于您要询问的是数学家，哲学家还是Ruby开发人员。我不是数学家也不是哲学家，但是我是Ruby开发人员，所以我可以告诉你1.5是0到无穷大之间的中点。

Range＃bsearch在一个范围内执行二进制搜索。例如，让我们用它来查找大于42（即43）的第一个整数，并查看它检查以找到它的值。

值= [] found_value =（0 ..）。 bsearch做|我values 42 end puts“大于42的整数是：＃{found_value}” puts“检查了以下值：” puts values

当我们将起始值更改为浮点数时，一位同事最近问我一些奇怪的行为。例如，考虑以下代码，该代码与上面的代码相同，但范围在0到Float :: INFINITY之间：

值= [] found_value =（0 .. Float :: INFINITY）。 bsearch做|我值 42末尾放置“大于42的浮点数是：＃{found_value}”末尾放置“检查了以下值：”末尾放置值

然后，我们在运行时会得到以下输出（请注意，由于输出太长，该输出已被截断）：

我们在二分搜索中检查的前几个值很奇怪：1.5、1.6759759912428246e + 154、1.5921412270130977e + 77，等等。这些数字从何而来？为了解释这些值，我们首先必须了解IEEE 754浮点数如何工作。

Ruby浮点数是双精度IEEE 754浮点数。如果您不了解如何在内存中表示浮点数的基础知识，那么互联网上有很多资源，这就是其中之一。

我们特别感兴趣的是如何在浮点数中表示无穷大。 “无穷大”是一个特殊值，其中指数位全为1，有效位（也称为小数或尾数）全为0。

Ruby的Range＃bsearch是通过名为range_bsearch的C函数实现的。它处理几种情况，而其中一个端点是浮点数的情况就是其中一种。在这种情况下，它会执行一个巧妙的技巧。它以64位整数（int64_t）1的形式读取Ruby float端点的C double类型。请注意，这与将double转换为整数类型不同，它直接将double读取为64位整数。你困惑吗？我确定是第一次阅读此代码的时间，因此如果您也喜欢，以后会更有意义。相信我。

让我们回顾一下如何在浮点数中表示无穷大。直观显示（通过出色的float.exposed网站的帮助）。我们可以看到符号为0（这是一个正值），所有指数位均为1，所有有效位均为0。

当然，0以浮点表示，所有位都设置为0。

那么，如果我们将端点的这些位当作整数读取，该怎么办？那么我们的范围是0到9218868437227405312。这个范围的中点是多少？现在是4609434218613702656。现在让我们将此值重新插入float.exposed。

使用相同的技术，现在您可以找到为什么二进制搜索之后会检查1.6759759912428246e + 154和1.5921412270130977e + 77的原因。这留给读者练习。

一旦将其包裹住，此方法的原因很简单。这是因为在浮点数中，更高有效的位始终位于更高有效的位置（而不是其右侧的位）。这对于重要意义显然是正确的。但这对指数也是正确的，因为仅增加有效位数就无法达到2的下一个幂，必须增加指数。因此，较大的指数将始终意味着浮点数具有较大的幅度。

一旦这是真的，我们就可以知道为什么使用这种技术进行二进制搜索。之所以起作用，是因为如果x和y是双精度数并且x> y，那么我们已经证明double_as_int64（x）> double_as_int64（y）也成立。这是二进制搜索的要求，因为值始终严格增加（技术上，二进制搜索仅要求单调增加，但严格增加比单调增加更严格的保证）。

Ruby在某个范围内的二进制搜索使用一种聪明的技术在端点加倍时执行二进制搜索，同时保持最坏情况下的运行时间O（n log n）。实际上，该技术并非特定于Ruby，可以在使用IEEE 754浮点数的任何语言中使用。