algorithm - 这个线性搜索实现真的有用吗？

Question

在Matters Computational我发现了这个有趣的线性搜索实现(它实际上是我的 Java 实现 ;-)):

public static int linearSearch(int[] a, int key) {
    int high = a.length - 1;
    int tmp  = a[high];

    // put a sentinel at the end of the array   
    a[high] = key;

    int i = 0;

    while (a[i] != key) {
        i++;
    }

    // restore original value
    a[high] = tmp;

    if (i == high && key != tmp) {
        return NOT_CONTAINED;
    }

    return i;
}

它基本上使用了一个哨兵，它是搜索值，因此您总能找到该值，而不必检查数组边界。最后一个元素存储在一个临时变量中，然后将哨兵放在最后一个位置。当找到该值时(记住，由于哨兵，它总是能找到)，恢复原始元素并检查索引是否代表最后一个索引并且不等于搜索到的值。如果是这种情况，则返回 -1 (NOT_CONTAINED)，否则返回索引。

虽然我发现这个实现非常聪明，但我想知道它是否真的有用。对于小数组，它似乎总是更慢，而对于大数组，它似乎只有在找不到值时才会更快。有什么想法吗？

编辑

最初的实现是用 C++ 编写的，因此可能会有所不同。

Answer 1

它不是线程安全的，例如，在第一个线程更改 a 后启动第二个线程可能会丢失您的 a[high] 值[high] 到key，所以会将key 记录到tmp，并在第一个线程恢复a 后结束[high] 到它的原始值。第二个线程会将 a[high] 恢复为它第一次看到的内容，这是第一个线程的 key。

它在 Java 中也没有用，因为 JVM 将对您的数组进行边界检查，因此您的 while 循环会检查您是否无论如何都不会越过数组的末尾。