为什么数组下标从0开始而不是1？Dijkstra的权威解答

为什么数组下标从0开始而不是1？Dijkstra的权威解答

很多初学者在学习编程时都会被数组下标从0开始而不是1的问题困扰。这个问题的答案，早在1972年就由图灵奖得主Dijkstra给出了。

Dijkstra，全名Edsger Wybe Dijkstra，是一位在计算机科学领域做出卓越贡献的荷兰科学家。他不仅提出了著名的Dijkstra最短路径算法，还发明了信号量和PV原语、银行家算法等重要概念。在1972年获得图灵奖时，他就已经对数组下标从0开始的问题给出了令人信服的解释。

一个简单的例子

让我们通过一个具体的例子来理解这个问题。假设我们需要用一个不等式来表示以下连续的整数序列：

[2,3,4,5,6,7,8,9,10,11,12]

这是一个包含11个数的序列。我们可以写出以下四个符合要求的不等式：

1. 2 <= i < 13
2. 1 < i <= 12
3. 2 <= i <= 12
4. 1 < i < 13

这些不等式都正确地表示了上述序列，但是否有理由选择其中的一种而不是另一种呢？

选择最优雅的表示方式

Dijkstra指出，选择1和2这两个不等式的原因在于它们有一个突出的优点：不等式边界的差（不等式右边 - 不等式左边）正好等于连续序列的长度。

进一步分析1和2的区别：

• 对于第1个不等式，左边（下界）等于序列中的最小值，右边（上界）大于序列中的最大值。
• 对于第2个不等式，左边（下界）小于序列中的最小值，右边（上界）等于序列中的最大值。

如果我们的序列是[0,1,2,3,4]，按照第2个不等式的写法，不等式的左边就会变成-1，这在表示全是自然数的序列时显得不够优雅。因此，第1个不等式是最优雅的选择。

数组下标的选择

接下来，我们需要决定数组的起始下标应该从1开始还是从0开始。根据不等式1的规则：

• 如果从下标1开始，下标范围是1 ≤ i < N+1
• 如果从下标0开始，下标范围是0 ≤ i < N

Dijkstra解释说，从下标0开始能够给出更好的不等式，因为元素的下标就等于序列中它前面的元素数（或者说“偏移量”）。

结论

通过这个简单的例子，我们可以看到为什么数组下标从0开始是一个更优雅的设计选择。这种设计不仅在数学上更加简洁，而且在实际编程中也更加直观和方便。

以下是Dijkstra的手稿，展示了他当年是如何思考这个问题的：