在有序数组中，找出一个项目不在数组中通常比找出它在数组中更快吗？
In an ordered array, is it generally faster to find out an item is not in the array than to find out it is?
在有序数组中，找出某项不在数组中通常比找出它在数组中更快吗？
我们老师问这个问题，我们大多说不是，但他的回答是是，速度更快。我真的不知道怎么可能。毕竟，要找出该项目不在数组中，我们必须进行最多的比较，但如果它在数组中，我们可能会在此之前找到它。
谁能解释一下？提前致谢。
考虑以下构造：让我们在数组中定义一个目标区域，其中包含相关元素可能所在的位置。当搜索算法开始时，目标区域是整个数组，因为我们还没有查看数组中的任何内容。
现在假设您进行二分查找（这最适合有序数组）。您会查看数组中间的元素。如果那个元素小于你正在寻找的元素，你就知道你正在寻找的元素一定在它的右边。因此，目标区域已缩小到阵列的右半部分。反之亦然：如果你看的元素更大，那么新的目标区域就是数组的左半部分。
如您所见，搜索算法的每一步都会以某种方式缩小目标区域，使您离答案越来越近。这适用于每个搜索算法。例如，如果您要线性迭代元素，则每一步都会将目标区域减少一个元素。
无论您是检查包含（该项目是否在数组中）还是排除（是否不在数组中），您的算法都会在以下两种情况之一停止：
- 在尝试缩小搜索范围时，您碰巧从数组中选择了一个元素，而这正是您要查找的项目。此时，包含测试将 return
true，或者排除测试将 return false.
- 目标区域已用尽（即减少为空集）。在这种情况下，包含产生
false，排除产生 true.
从这个推理可以得出包含和排除测试是完全对称的，因此我同意你的"no"。但是，请务必请您的老师解释他的推理，然后 post 在这里。
在有序数组中，找出某项不在数组中通常比找出它在数组中更快吗？
我们老师问这个问题，我们大多说不是，但他的回答是是，速度更快。我真的不知道怎么可能。毕竟，要找出该项目不在数组中，我们必须进行最多的比较，但如果它在数组中，我们可能会在此之前找到它。
谁能解释一下？提前致谢。
考虑以下构造：让我们在数组中定义一个目标区域，其中包含相关元素可能所在的位置。当搜索算法开始时，目标区域是整个数组，因为我们还没有查看数组中的任何内容。
现在假设您进行二分查找（这最适合有序数组）。您会查看数组中间的元素。如果那个元素小于你正在寻找的元素，你就知道你正在寻找的元素一定在它的右边。因此，目标区域已缩小到阵列的右半部分。反之亦然：如果你看的元素更大，那么新的目标区域就是数组的左半部分。
如您所见，搜索算法的每一步都会以某种方式缩小目标区域，使您离答案越来越近。这适用于每个搜索算法。例如，如果您要线性迭代元素，则每一步都会将目标区域减少一个元素。
无论您是检查包含（该项目是否在数组中）还是排除（是否不在数组中），您的算法都会在以下两种情况之一停止：
- 在尝试缩小搜索范围时，您碰巧从数组中选择了一个元素，而这正是您要查找的项目。此时，包含测试将 return
true，或者排除测试将 returnfalse. - 目标区域已用尽（即减少为空集）。在这种情况下，包含产生
false，排除产生true.
从这个推理可以得出包含和排除测试是完全对称的，因此我同意你的"no"。但是，请务必请您的老师解释他的推理，然后 post 在这里。