我真的不喜欢问关于家庭作业的问题，但是这个问题把我难住了。答案似乎应该如此简单，但我却想不起来!
这个问题来自"数据结构和算法"。由Harry Lewis和Larry Denenberg提出，第一章第一个问题。我们有一个简单的for循环用于顺序搜索。
function SequentialSearch(table T[0...n-1], key K): integer
{Return position of K in table T, if it is present, otherwise -1}
for i from 0 to n - 1 do
if T[i] = K then return i
return -1
很简单，对吧?好的，对于这个循环的每次迭代，有两个检查:(1)检查T[i]是否= K，(2)检查i是否>N - 1。每个循环迭代的运行时是一个常量2。问题是:如何将运行时间减少到1?我怎样才能不去检查它是否存在呢?N - 1(即，如果已经到达表的末端)?
给我们的提示是可以使用哨兵值。嗯，这很简单，除了一个问题，那就是:检查哨兵值如何比检查表的长度改善运行时?不管我是检查表的长度还是检查哨兵值，每次迭代的运行时不是仍然是2吗?
我不期望在这里得到答案。(答案将用伪代码编写。)我只是在如何实现这一点，以减少运行时难住。对我来说，它似乎被简化到尽可能少，但我知道什么?
谢谢!
提示一下:您放入T[n]中的哨兵值不必在每次算法运行时都相同。它可以依赖于K，也就是你要找的值。这有帮助吗?