IEEE 754（IEEE二进制浮点数算术标准）是 20 世纪 80 年代以来使用最广泛的浮点数运算标准，被许多 CPU 与浮点运算器所采用。

在上世纪六、七十年代，各家计算机公司的各个型号计算机，有着千差万别的浮点数表示，这给数据交换、计算机协同工作造成了极大不便。

在 1980 年，英特尔公司就推出了单片的 8087 浮点数协处理器，其浮点数表示法及定义的运算具有足够的合理性、先进性，被 IEEE 采用作为浮点数的标准，于 1985 年发布。因此第一个标准就是 IEEE 754-1985。

科学计数法

先来说说科学计数法。科学计数法大家肯定都不陌生，它是一种数字的表示法，最早由阿基米德提出。在科学记数法中，一个数被写成一个实数 a 与一个 10 的 n 次幂的积的形式：

1

value = a * 10ⁿ

其中：

• n 必须是一个整数
• 1 ≤ |a| < 10（如果 |a| 是一个小于 1 的小数，或大于等于 10 的数，都可以通过改变 n 来表示）
• a 是一个实数，称为有效数或尾数(mantissa)

科学计数法的优点是：当需要表示非常大或非常小的数时，如果用一般的方法，要将一个数的所有位数都写出来，很难直接明确知道它的大小，还会浪费很多空间。如果使用科学记数法来表示，一个数的数量级、精确度和数值都会非常直观。

比如，0.00000000000000000000000167262158 的科学计数法表示为 1.67262158 * 10⁻²⁴；1898130000000000000000000000 的科学计数法表示为 1.89813 * 10²⁷。

为什么要先说科学计数法呢？因为 IEEE 754 标准的表示方法几乎就是二进制的科学计数法。

表示

IEEE 754 规定了四种表示浮点数值的方式：单精确度（32位）、双精确度（64位）、延伸单精确度（43比特以上，很少使用）与延伸双精确度（79比特以上，通常以80位实现）。

本文主要的研究对象是单精确度浮点数（32位）。其他精度，比如双精确度浮点数（64位），其和单精确度其实是大同小异的。

二进制浮点数的表示如下：

1

value = sign * exponent * fraction

其中

• sign(sign bit)：符号位
• exponent(exponent bias)：指数偏移值
• fraction：分数值

二进制浮点数的组成如下图：

对照上图，单精确度浮点数（32位）表示如下：

双精确度浮点数（64位）表示如下：

一些概念

下面解释一些概念。

（1）符号位(sign bit)

符号位为 0 表示正数，符号位为 1 表示负数。

（2）指数的实际值

一个数二进制科学计数法表示下的指数的值。

例如 2¹⁷，那么指数的实际值就是 17。

（3）指数偏移值(exponent bias)

指的是根据 IEEE 754 标准对浮点数二进制表示中指数部分编码的值：

1

exponent bias = 指数的实际值 + 某个固定值

IEEE 754 标准规定：该固定值为 2ᵉ⁻¹ - 1，e 为存储指数的比特的长度。

例如，单精度浮点数的指数域是 8 个比特，那么固定偏移值为 2⁸⁻¹ - 1 = 128 - 1 = 127。如果指数实际值为17₁₀，那么在单精度浮点数中的指数域编码值为 17₁₀ + 127₁₀ = 144₁₀。

为什么要用这种形式来表示浮点数的指数呢？

因为这样可以用长度为 e 个比特的无符号整数来表示所有的指数取值，这使得两个浮点数的指数大小的比较也更为容易，实际上可以直接按照字典次序比较两个浮点表示的大小。

这种移码表示的指数部分，中文称作阶码。

normal number

normal number：规约形式的浮点数。

“规约”指的是用唯一确定的浮点形式去表示一个值。

如果浮点数中指数部分的编码值范围为 (0, 2ᵉ - 2]（即指数位不全为 0，也不全为 1），且在科学表示法的表示方式下，fraction 部分的最高有效位是 1（fraction 部分的范围是 [1, 2)），那么这个浮点数被称为规约形式的浮点数。

因此，规约形式的单精度浮点数的指数部分编码值范围为 (0, 254]，这也可以反推出规约形式的单精度浮点数对应的指数部分实际取值是 [-126, 127]。

为什么没有 -127 和 128 呢？因为 -127 和 128 被用作特殊值处理，见下面“非规约形式的浮点数”和“特殊值”。

由于这种表示下的尾数有一位隐含的二进制有效数字，为了与二进制科学计数法的尾数相区别，IEEE 754 称之为有效数（significant）。

subnormal number

subnormal number：非规约形式的浮点数。

为什么需要非规约形式的浮点数？

由规约形式的浮点数部分的内容，我们可以推算出，规约形式的单精度浮点数的取值范围为：

1
2
3

±尾数 * 2 ^ 指数
= ±[1, 2) * 2 ^ [-126, 127]
= (-2 * 2¹²⁷, -1 * 2⁻¹²⁶] ∪ [1 * 2⁻¹²⁶, 2 * 2¹²⁷)

转换为十进制后的大致范围是：

1

[-3.4 * 10³⁸, -1.18 * 10⁻³⁸] ∪ [1.18 * 10⁻³⁸, 3.4 * 10³⁸]

这里就有个问题，使用规约形式的浮点数我们无法表示非常接近 0 的极小的数（即 (-1 * 2⁻¹²⁶, 1 * 2⁻¹²⁶) 之间的数）！非规约形式的浮点数的出现就将解决这个问题。

什么是非规约形式的浮点数？

如果浮点数的指数部分的编码值是 0（即指数位全为 0），且 fraction 部分非零（fraction 部分的最高有效位是 0，fraction 部分的范围是 (0, 1)），那么这个浮点数被称为非规约形式的浮点数。

IEEE 754 标准规定：非规约形式的浮点数的指数偏移值比规约形式的浮点数的指数偏移值小 1。

例如，最小的规约形式的单精度浮点数的指数部分编码值为 1，指数的实际值为 -126；而非规约的单精度浮点数的指数域编码值为 0，对应的指数实际值也是 -126 而不是 -127，这是规定。至于为什么这么规定，下面会说到。

非规约形式的浮点数怎么表示非常接近 0 的数？

准确来说，这个问题应该是非规约形式的浮点数怎么表示 (-1 * 2⁻¹²⁶, 1 * 2⁻¹²⁶) 之间的数？

同样，我们可以推算出非规约形式的单精度浮点数的取值范围为：

1
2
3

±尾数 * 2 ^ 指数
= ±(0, 1) * 2⁻¹²⁶
= (-1 * 2⁻¹²⁶, 0) ∪ (0, 1 * 2⁻¹²⁶]

仔细看下，非规约形式的单精度浮点数的区间范围和规约形式的单精度浮点数的区间范围正好构成了 (-2 * 2¹²⁷, 0) ∪ (0, 1 * 2 * 2¹²⁷)。

（是不是中间少个 0 很难受，不要急，0 是作为特殊值存在的，见下面的“特殊值”）

什么是渐进式下溢出(gradual underflow)？

根据前面的内容我们可以知道：

非规约形式的单精度浮点数的最大值为 0 00000000 1111111111111111111111，其实就是 0.1111111111111111111111 * 2⁻¹²⁶

规约形式的单精度浮点数的最小值（大于 0 的区间中）为 0 00000001 0000000000000000000000，其实就是 1.0000000000000000000000 * 2⁻¹²⁶

可以看到，两者之间几乎实现了平滑的过度，非规约形式的单精度浮点数的最大值非常紧密的连接上了规约形式的单精度浮点数的最小值（大于 0 的区间中，小于 0 的区间也同理）。

这种特性在 IEEE 754 中就称为*渐进式下溢出(gradual underflow)*。

理解了这个特性，也就解释了前面的两个疑问：

1. 为什么规定非规约形式浮点数的尾数前隐藏的整数部分是 0，而规约形式浮点数尾数前隐藏的整数部分是 1 ？
2. 为什么规定非规约形式浮点数的指数实际值的计算公式是 1 - bias，而规约形式浮点数的指数实际值计算公式是 指数部分的值 - bias ？

就是因为有这些规定才能实现渐进式下溢出这种特性。

还有一个概念与之对应，就是*突然式下溢出(abrupt underflow)*。顾名思义，不解释了。

non-number

non-number：特殊值。

有三个特殊值：

• 如果指数是 0 并且 fraction 的小数部分是 0，这个数是 ±0（和符号位相关）
• 如果指数是 2ᵉ - 1 并且 fraction 的小数部分是 0，这个数是 ±∞（和符号位相关）
  • 什么是 ±∞ 呢？比如对于规约形式的单精度浮点数来说，存储的值超过了它的范围，比如存储的值是 4 * 10³⁸
• 如果指数是 2ᵉ - 1 并且 fraction 的小数部分非 0，这个数表示为非数（NaN）
  • 什么是 ±∞ 呢？比如要存储的值是 √-1

总结

以上规则，可总结如下：

凑字数

网上有几篇文章我觉得写得挺不错，我也参考了部分内容，这里共享出来链接以供大家阅读：

https://www.bilibili.com/read/cv4546492
https://www.jianshu.com/u/9d6b8017232d

鉴于这篇已经写了这么多字，就先打住，下篇会用具体示例再来演示一下。

十进制整数 N 可以表示为 N₁₀，二进制整数 N 可以表示为 N₂。

重要：为了简洁说明，约定本文以下内容中都使用一个字节，也就是 8 个 bit 来表示二进制数。

正整数转二进制

除 2 取余直到商为 0 时为止，然后倒序排列余数，最后高位补 0。

举例：将 42 转换为二进制
除二取余直到商为 0 时为止

• 42 / 2 = 21 ⋯⋯ 0
  • 21 / 2 = 10 ⋯⋯ 1
  • 10 / 2 = 5 ⋯⋯ 0
  • 5 / 2 = 2 ⋯⋯ 1
  • 2 / 2 = 1 ⋯⋯ 0
  • 1 / 2 = 0 ⋯⋯ 1
• 倒序排列余数为 101010
• 高位补 0 为 00101010

所以，(42)₁₀ = (00101010)₂

负整数转二进制

在前面的文章中我们知道，负数在计算机中以原码的补码形式表示。

举例：将 -42 转换为二进制

• (42)₁₀ = (00101010)₂
• -42 的原码为 10101010
• 反码为 11010101
• 补码为 11010110

所以，(-42)₁₀ = (11010110)₂

小数转二进制

整数部分同正整数转二进制；小数部分乘以 2，取结果的整数部分，直到小数部分为 0 （此时二进制的最后一位为 0 或 1）或者位数已达到所要求的精度为止。然后把每次结果的整数部分按先后次序排列，即可得到二进制小数部分序列。

举例：将 42.125 转换为二进制

• 整数部分 (42)₁₀ = (00101010)₂
• 小数部分乘以 2，取结果的整数部分，直到小数部分为 0 或者位数已达到所要求的精度为止
  • 0.125 * 2 = 0.25，整数部分为 0
  • 0.25 * 2 = 0.5，整数部分为 0
  • 0.5 * 2 = 1，整数部分为 1
• 把每次结果的整数部分按先后次序排列为 001

所以，(42.125)₁₀ = (00101010.001)₂

二进制转十进制

（1）首位是 0 代表正整数，从右到左用二进制的每个数去乘以 2 的相应次方并递增。

举例：将 00101010 转换为十进制

1
2
3
4

0 * 2⁰ + 1 * 2¹ + 0 * 2² + 1 * 2³ + 0 * 2⁴ + 1 * 2⁵ + 0 * 2⁶
= 1 * 2¹ + 1 * 2³ + 1 * 2⁵
= 2 + 8 + 32
= 42

加上符号为 42，所以，(00101010)₂ = (42)₁₀

（2）首位是 1 代表负整数，先转成原码，再参考上面的方法。

举例：将 11010110 转换为十进制

• 反码为 11010101
• 原码为 10101010

1
2
3
4

0 * 2⁰ + 1 * 2¹ + 0 * 2² + 1 * 2³ + 0 * 2⁴ + 1 * 2⁵ + 0 * 2⁶
= 1 * 2¹ + 1 * 2³ + 1 * 2⁵
= 2 + 8 + 32
= 42

加上符号为 -42，所以，(11010110)₂ = (-42)₁₀

（3）小数是将小数点后从左往右乘以二的相应负次方并递减。

举例：将 00101010.001 转换为十进制

• 整数部分 (00101010)₂ = (42)₁₀
• 小数部分为 0 * 2⁻¹ + 0 * 2⁻² + 1 * 2⁻³ = 1 * 2⁻³ = 0.125

所以，(00101010.001)₂ = (42.125)₁₀

凑字数

当然，浮点数在计算机中不可能这么表示，它也有自己的一套标准。

浮点数的部分可以先暂且这么理解，关于IEEE二进制浮点数算术标准（IEEE 754）后面的文章会再说

二进制和十进制的互转方法，你搞懂了吗？

搞懂了上篇文章，这篇就会比较容易。上篇文章传送门：搞懂原码、反码、补码

在 Java 中有三个位移运算：

1. <<：左移
2. >>：右移
3. >>>：无符号右移

正数位移运算

首先来看结果：

十进制 2 转换为二进制原码、反码、补码都为 00000000 00000000 00000000 00000010

2 << 1

• 符号位固定不动，二进制左移一位，高位丢弃，低位补 0，结果为 00000000 00000000 00000000 00000100
• 其反码、原码都和该补码一样
• 换算成十进制为 4

2 >> 1：

• 符号位固定不动，二进制右移一位，低位丢弃，高位补 0，结果为 00000000 00000000 00000000 00000001
• 其反码、原码都和该补码一样
• 换算成十进制为 1

负数位移运算

首先来看结果：

十进制 -2 转换为二进制原码为 10000000 00000000 00000000 00000010，反码为 11111111 11111111 11111111 11111101，补码为 11111111 11111111 11111111 11111110

-2 << 1：

• 符号位固定不动，二进制左移一位，高位丢弃，低位补 0，结果为 11111111 11111111 11111111 11111100
• 该补码对应的反码为 11111111 11111111 11111111 11111011
• 该反码对应的原码为 10000000 00000000 00000000 00000100
• 换算成十进制为 -4

-2 >> 1：

• 符号位固定不动，二进制右移一位，低位丢弃，高位补 1，结果为 11111111 11111111 11111111 11111111
• 该补码对应的反码为 11111111 11111111 11111111 11111110
• 该反码对应的原码为 10000000 00000000 00000000 00000001
• 换算成十进制为 -1

无符号右移

首先来看结果：

前面 << 和 >> 都是符号位固定不动，而无符号右移则是符号位跟着一起右移。

十进制 2 转换为二进制补码为 00000000 00000000 00000000 00000010；十进制 -2 转换为二进制补码为 11111111 11111111 11111111 11111110

2 >>> 1：

• 二进制符号位跟着右移，低位丢弃，高位补 0，结果为 00000000 00000000 00000000 00000001
• 其反码、原码都和该补码一样
• 换算成十进制为 1

-2 >>> 1：

• 二进制符号位跟着右移，低位丢弃，高位补 0，结果为 01111111 11111111 11111111 11111111
• 其反码、原码都和该补码一样
• 换算成十进制为 2147483647

无符号右移有个经典应用，在之前二分查找的文章中也说过，就是求两个整数的平均值：int mid = (l + r) >>> 1

位移运算，你搞懂了吗？

在本文开始前，先抛出一个问题：在计算机系统中，数字一律用补码的形式来表示和存储。为什么？

希望通过本文能够解释这个问题。

重要：为了简洁说明，约定本文以下内容中都使用一个字节，也就是 8 个 bit 来表示二进制数。

原码

原码（True form）是指“未经更改”的码，是指一个二进制数左边加上符号位后所得到的码。

计算机中所有的数字均用 0 和 1 编码表示，数字的正负号也不例外，如果一个机器数字长是 n 位的话，约定最左边 1 位用作符号位，其余 n - 1 位用于表示数值，这部分也称为数值域。

因此，当二进制数大于 0 时，符号位为 0；当二进制数小于 0 时，符号位为 1；当二进制数等于 0 时，符号位可以为 0 或 1 (+0 / -0)。

举个例子：

可以看到，一个数字用二进制原码表示的话，其取值范围是 -111 1111 ~ +111 1111，换算成十进制就是 -127 ~ +127。

为了便于算术逻辑单元（Arithmetic Logic Unit, ALU）的设计，后面又发展出了反码、补码等经过转换过的码。

反码

对于二进制数而言，对其进行取反操作就是将 0 变为 1，1 变为 0。

正数的反码（Ones’ complement）等于其原码，负数的反码则通过保留其符号位，然后将原码的数值位取反得到。

举个例子：

为什么会出现反码？

在数学中有加减乘除四则运算，但这对于计算机而言却太麻烦了。我们希望最好能够只有一种情况，比如只有加法，这样才能够让计算机变得简单高效。

而这完全可以做到。举个例子，在数学中 5 - 3 = 2，它完全等价于 5 + (-3) = 2，这样就做到了用加法来表示减法，而乘法是加法的累积（例如 3 * 5 = 3 + 3 + 3 + 3 + 3 = 15），除法是减法的累积（例如 10 / 3 = 10 - 3 - 3 - 3 = 1 mod 3）。所以在计算机中只有加法就够了。

但是，如果直接用原码来进行加法，计算机需要先识别该二进制原码的符号位，来确定该数字是正数还是负数，然后再进行加法运算，这样显然效率不高。

为了提高效率，让计算机能够在运算时统一处理符号位和数值域，或者说让符号位也能参与运算，所以就产生了反码。

至此，问题好像得到了解决。接下来我们验证一下。

仍然以上面的 5 - 3 为例：5 的原码为 0000 0101，反码为 0000 0101；-3 的原码为 1000 0011，反码为 1111 1100。

1
2
3
4
5
6

5 - 3
= 5 + (-3)
= 0000 0101(反码) + 1111 1100(反码)
= 0000 0001(反码)
= 0000 0001(原码)
= 1

结果竟然差了 1 ？！

不急，我们再来看两个特殊的运算：

1
2
3
4
5
6

1 - 1
= 1 + (-1)
= 0000 0001(反码) + 1111 1110(反码)
= 1111 1111(反码)
= 1000 0000(原码)
= -0

1
2
3
4
5

0 + 0
= 0000 0000(反码) + 0000 0000(反码)
= 0000 0000(反码)
= 0000 0000(原码)
= 0

可以看到，虽然 -0 和 0 是一样的，但是在反码中却有两种表示方式。也可以这么理解：当用一个字节表示数字的取值范围时，这些数字中多了个 -0。

因此，虽然用反码进行运算时符号位可以直接参加运算，但是结果却是不对的。

补码

补码（Two’s complement）的出现就是为了解决上面反码的问题。

正数的补码和其原码、反码一样，负数的补码是其反码 + 1。

举个例子：

同样，接下来我们用补码验证一下。

仍然以 5 - 3 为例：5 的原码为 0000 0101，反码为 0000 0101，补码为 0000 0101；-3 的原码为 1000 0011，反码为 1111 1100，补码为 1111 1101。

1
2
3
4
5
6

5 - 3
= 5 + (-3)
= 0000 0101(补码) + 1111 1101(补码)
= 0000 0010(补码)
= 0000 0010(原码)
= 2

结果没问题。再来看那两个特殊的运算：

1
2
3
4
5
6

1 - 1
= 1 + (-1)
= 0000 0001(补码) + 1111 1111(补码)
= 0000 0000(补码)
= 0000 0000(原码)
= 0

1
2
3
4
5

0 + 0
= 0000 0000(补码) + 0000 0000(补码)
= 0000 0000(补码)
= 0000 0000(原码)
= 0

结果仍然没问题，至此，问题终于得到了解决。

同时这也解释了一开始的问题，在计算机系统中，数字一律用补码的形式来表示和存储。

原码、反码、补码，你搞懂了吗？

之前在插入排序的文章中介绍了一个用二分查找来优化的思路，但是没有细说二分查找，今天也算是补上这个坑。刚好也是 leetcode 上的一道题。

二分查找算法（binary search algorithm），也称折半搜索算法（half-interval search algorithm）、对数搜索算法（logarithmic search algorithm）等。

思想

二分查找法是一种在有序数组中查找某一特定元素的搜索算法，它的思想比较简单：

1. 从有序数组的中间元素开始搜索，如果中间元素正好是要查找的元素，则搜索过程结束；
2. 如果要查找的元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中进行查找，而且跟开始一样也从中间元素开始；
3. 如果在某一步中数组为空，则代表要查找的元素不在数组中。

中间元素

二分查找每次都从有序数组的中间元素开始，那必然要先找到中间元素的索引值 mid。假设有序数组 nums 的第一个元素索引值记为 l，最后一个元素索引值记为 r，怎么求 mid 的值呢？

很简单，小学数学就学过：mid = (l + r) / 2。但是，在程序里可不一定是这样，前面在leetcode之7-整数反转的文章里我们知道，整数是有范围的。虽然 l 和 r 都是正常的整数，但是 l + r 就有可能会超过整数的范围，也就是说会有溢出的风险。

那如何安全的求两个整数的平均值呢？

（1）你可能会想了， (l + r) / 2 改成 l / 2 + r / 2 不就行了吗？在数学里确实是这样，但是我们讨论的是在程序里的情况。举个例子，l = 1，r = 3，那么 mid = 1 / 2 + 3 / 2 = 0 + 1 = 1，但其实正确结果应该是 2。

（2）换个角度来思考一下，既然我们知道了 l 和 r，那么我们给 l 加上 r - l 偏移量的一半不就行了，毕竟减法是不会溢出的。即 mid = l + (r - l) / 2。

（3）看看大师们是如何解决这个问题的。java 类库中也提供了二分搜索的方法，我们来看看源码中是怎样写的：mid = (l + r) >>> 1。

这么写就不怕 l + r 溢出了吗？不要震惊，仔细看后面是 >>> 1（无符号右移），而不是 >> 1（带符号右移），所以并没有问题。

其实也非常容易理解，如果我不把结果二进制的最高位当作符号来看，那溢不溢出又有什么关系呢？果然，大师的脑回路就是不一样。

注意事项

二分查找的思想比较简单，但是代码写起来却不太容易，因为有很多边界问题需要注意，所以我们一定要明确变量的含义，要记住一点：改变取值不代表改变含义。

举个例子，r 应该怎么取值？是取 nums.length 还是取 nums.length - 1 ？其实都可以，只是我们在写代码的过程中一定要注意不能改变 r 取值的含义。

非递归代码

定义要在 [l…r] 的范围里寻找 target，也就规定了 r = nums.length - 1。

值得一提的是，java 类库中提供的二分搜索用的就是这个定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 在有序数组 nums 里查找元素 target
 * @param nums 有序数组
 * @param target 要查找的元素
 * @return 元素 target 的索引，如果没找到返回 -1
 */
public int binarySearch(int[] nums, int target){
    // 定义在 [l...r] 的范围里寻找 target（边界问题：r）
    int l = 0, r = nums.length - 1;
    // 当 l == r 时,区间 [l...r] 依然是有效的（边界问题：l < r or l <= r ？这就需要明确 l 和 r 的定义）
    while (l <= r) {
        int mid = (l + r) >>> 1;
        if (target > nums[mid]) {
            // 说明 target 在 [mid+1...r] 中（边界问题：l = mid or l = mid + 1 ？这就需要明确 l 和 r 的定义）
            l = mid + 1;
        } else if (target < nums[mid]) {
            // 说明 target 在 [l...mid-1] 中（边界问题：r = mid or r = mid - 1 ？这就需要明确 l 和 r 的定义）
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

定义要在 [l…r) 的范围里寻找 target，也就规定了 r = nums.length。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 在有序数组 nums 里查找元素 target
 * @param nums 有序数组
 * @param target 要查找的元素
 * @return 元素 target 的索引，如果没找到返回 -1 
 */
public int binarySearch(int[] nums, int target){
    // 定义在 [l...r) 的范围里寻找 target（边界问题：r）
    int l = 0, r = nums.length;
    // 当 l == r 时, 区间 [l...r) 是个无效区间（边界问题：l < r or l <= r ？这就需要明确 l 和 r 的定义）
    while (l < r) {
        int mid = (l + r) >>> 1;
        if (target > nums[mid]) {
            // 说明 target 在 [mid+1...r) 中（边界问题：l = mid or l = mid + 1 ？这就需要明确 l 和 r 的定义）
            l = mid + 1;
        } else if (target < nums[mid]) {
            // 说明 target 在 [l...mid) 中（边界问题：r = mid or r = mid - 1 ？这就需要明确 l 和 r 的定义）
            r = mid;
        } else {
            return mid;
        }
    }
    return -1;
}

递归代码

从二分查找思想的描述中，明显有一种递归的感觉，确实，二分查找也可以用递归的方式来写。这里同样给出两种不同定义的写法。

定义要在 [l…r] 的范围里寻找 target，也就规定了 r = nums.length - 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * 在有序数组 nums 里查找元素 target
 * @param nums 有序数组
 * @param target 要查找的元素
 * @return 元素 target 的索引，如果没找到返回 -1 
 */
public int binarySearch(int[] nums, int target){
    // 定义在 [l...r] 的范围里寻找 target
    return binarySearchHelp(nums, 0, nums.length - 1, target);
}

private int binarySearchHelp(int[] nums, int l, int r, int target) {
    // 边界问题, 同上
    if (l > r) {
        return -1;
    }
    int mid = (l + r) >>> 1;
    if (nums[mid] > target) {
        // 边界问题, 同上
        return binarySearchHelp(nums, l, mid - 1, target);
    } else if (nums[mid] < target) {
        // 边界问题, 同上
        return binarySearchHelp(nums, mid + 1, r, target);
    }
    return mid;
}

定义要在 [l…r) 的范围里寻找 target，也就规定了 r = nums.length。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * 在有序数组 nums 里查找元素 target
 * @param nums 有序数组
 * @param target 要查找的元素
 * @return 元素 target 的索引，如果没找到返回 -1 
 */
public int binarySearch(int[] nums, int target){
    // 定义在 [l...r) 的范围里寻找 target
    return binarySearchHelp(nums, 0, nums.length, target);
}

private int binarySearchHelp(int[] nums, int l, int r, int target) {
    // 边界问题, 同上
    if (l >= r) {
        return -1;
    }
    int mid = (l + r) >>> 1;
    if (nums[mid] > target) {
        // 边界问题, 同上
        return binarySearchHelp(nums, l, mid, target);
    } else if (nums[mid] < target) {
        // 边界问题, 同上
        return binarySearchHelp(nums, mid + 1, r, target);
    }
    return mid;
}

复杂度分析

1. 时间复杂度：

• 二分查找每次比较都使搜索范围缩小一半（每次都除以 2），所以时间复杂度为 O(logn)。

2. 空间复杂度：

• 对于非递归代码来说，没有使用额外的空间，所以空间复杂度为 O(1)；

• 对于递归代码来说，因为递归的次数和深度都是 logn，所以空间复杂度也为 O(logn)。

凑字数

二分查找法真是完美的说明了：思考一个算法的思想是简单的，但是写出一个没有 bug 的程序却是复杂的。