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

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索引，并进行“跳转”。

如果在该循环中设置了immediately.，则该循环应退出

1. 当设置了LOW时，+ 1也是错误的，因为它不认为前面的元素可能是要查找的值。

1. 尽管有一个用于特定lower_bound的参数，但此变量仅在开始时用于LOW的初始化，但在实际访问A时从未使用过。

1. 奇怪的是，N是一个参数，因为逻辑上是N = upper_bound - lower_bound + 1。所以这只会导致更多的inconsistency.

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