跳转搜索算法:伪代码错误

Question

我正在读一本关于数据结构和算法的书，目前我正在读关于跳转搜索算法的书。我认为书中的伪代码有错误(请检查下面打印的代码(。在步骤3期间不执行跳转，因此以下算法的运行时间为O(n(阶(并且正确实现的跳转搜索算法的运行时为O(sqrt(n((。

总而言之，我认为跳转搜索算法中存在错误，但我可能错了，如果有任何帮助/评论，我将不胜感激。非常感谢。

**JUMP_SEARCH (A, lower_bound, upper_bound, VAL, N)**
Step 1: [INITIALIZE] SET STEP = sqrt(N), I = 0, LOW = lower_bound, HIGH = upper_bound, POS = –1
Step 2: Repeat Step 3 while I < STEP
Step 3:
IF VAL < A[STEP]
SET HIGH = STEP – 1
ELSE
SET LOW = STEP + 1
[END OF IF]
SET I = I + 1
[END OF LOOP]
Step 4: SET I = LOW
Step 5: Repeat Step 6 while I <= HIGH
Step 6:
IF A[I] = Val
POS = I
PRINT POS
Go to Step 8
[END OF IF]
SET I = I + 1
[END OF LOOP]
Step 7: IF POS = –1
PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
[END OF IF]
Step 8: EXIT

Answer 1

你说得绝对正确。伪代码有很多问题：

1. 步骤3总是进行与循环中未修改STEP相同的比较。因此，这意味着在这个循环中，要么设置了HIGH，要么设置LOW，但从来没有设置两者。如果设置了LOW，则搜索仍将采用O(n(，正如您正确指出的那样。A的索引应该在该循环中改变；跳跃"；。

2. 当在该循环中设置HIGH时，该循环应立即退出。

3. 当设置了LOW时，+ 1也是错误的，因为它没有考虑到前面的元素可能是要查找的值。

4. 即使有一个特定lower_bound的参数，这个变量在开始时只用于LOW的初始化，但在实际访问A时，它永远不会被使用。

5. 奇怪的是N是一个参数，因为在逻辑上N = upper_bound - lower_bound + 1。因此，这只会导致进一步的不一致。

结论：这个伪代码中有太多错误，对它没有帮助。