MIT软件构造课程：设计规格说明与查找算法解析

"这篇资料是麻省理工学院2018年春季软件构造课程的一份阅读材料，主题聚焦于设计规格说明，特别是关于在数组中查找特定元素的算法设计。内容涉及了`findFirst`、`findLast`以及`findExactlyOne`等方法的实现，并探讨了确定性和非确定性在查找算法中的应用。" 在软件构造中，设计规格说明是非常关键的一部分，它清晰地定义了软件系统或组件的行为和预期结果。这份阅读材料主要关注在数组中寻找特定值的算法设计，这对于理解和编写高效、准确的代码至关重要。 1. **findFirst** 和 **findLast** 方法： 这两个方法分别用于找到数组中第一个和最后一个等于给定值的元素的索引。`findFirst`从数组的开头开始遍历，而`findLast`从数组的末尾开始遍历。如果找不到匹配的元素，`findFirst`返回数组长度，表示没有找到；`findLast`返回-1，表示同样未找到。 ```java static int findFirst(int[] arr, int val) { for (int i = 0; i < arr.length; i++) { if (arr[i] == val) return i; } return arr.length; } static int findLast(int[] arr, int val) { for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] == val) return i; } return -1; } ``` 2. **findExactlyOne** 方法： 此方法要求输入数组中给定值出现且仅出现一次。它确保返回该值的唯一索引。如果值在数组中不唯一或不存在，该方法可能会引发异常或返回错误的结果。 ```java static int findExactlyOne(int[] arr, int val) { // requires: val occurs exactly once in arr // effects: returns index i such that arr[i] = val } ``` 3. **findOneOrMore, AnyIndex** 方法： 这个方法要求输入数组中至少有一个值匹配，然后返回任意一个匹配值的索引。这与`findExactlyOne`不同，因为它并不关心匹配的元素数量，只要存在匹配项即可。 4. **Underdetermined 和 Nondeterministic**： 文档提到了“underdetermined”和“nondeterministic”的概念。在查找算法中，如果一个操作的结果可以有多种可能，那么它就是不确定的或非确定性的。例如，如果没有明确指定返回哪个匹配项时，`findFirst`和`findLast`可能被认为是不确定的，因为它们可以返回任何匹配的元素，但通常我们期望它们返回的是第一个或最后一个。 5. **示例和讨论**： 材料通过一些示例，如`[1,2,2], 2`，`[1,2,3], 2`和`[1,2,2], 4`，来阐述查找算法在不同情况下的行为。特别是`findFirst`方法的示例，强调了正确处理数组中没有匹配项的情况。 这些设计规格说明不仅涵盖了基本的算法实现，还涉及了对算法行为的明确描述，这对于确保软件的正确性和可预测性至关重要。在实际编程中，理解并能正确应用这些方法对于解决实际问题非常有帮助。