顺序查找如何移除表尾边界检查 将单次循环运行开销从2降为1

核心逻辑解答 #

你产生疑问的核心原因是误以为哨兵检查是独立于原有键值比对的额外步骤，实际上两者是完全合并的，没有新增开销，反而省掉了原有的边界检查步骤：

• 原循环的两次开销来源：
  1. 每次迭代首先要做边界检查：判断i是否小于等于n-1，满足才会进入循环体
  2. 进入循环体后再做键值比对：判断T[i]是否等于K
     因此单次迭代固定产生两次比较操作，开销为2。
• 哨兵优化的核心设计：
  你只需要提前在原数组的末尾（索引为n的位置，原数组有效元素到n-1为止）写入目标值K作为哨兵，此时整个待查序列里必然存在至少一个K：要么是原数组里的目标元素，要么是末尾的哨兵。
  这种情况下你完全可以去掉循环的边界检查，只保留T[i] == K的比对逻辑：循环一定会在i = n时因为碰到哨兵自动终止，永远不会出现越界的情况。
  此时单次循环就只有一次比较操作，开销直接降到1，原有边界检查的功能已经被「哨兵+键值比对」的组合完全替代了，没有额外操作。
• 收尾的一次判断不属于迭代开销：
  循环终止后你只需要做一次判断：如果i < n，说明是在原数组有效范围内找到的目标，返回i；否则说明是碰到了哨兵，原数组无目标值，返回-1。这一步仅在循环结束后执行一次，不会增加单次迭代的开销。

内容的提问来源于stack exchange，提问作者OldLavyGenes474