二进制数据中无重复的二进制搜索

Question

我正在考虑以下问题，

给出大小为n的排序数组，其中包含没有重复的整数，我们可以比使用以下属性的普通二进制搜索做得更好吗？>

• a）没有重复项
• b）两个相邻整数之间没有整数

想法是，当您遇到一个值时，您将添加一个测试以查看所寻找的值是否与当前值（+或-1）相邻，如果是，则将搜索间隔（而不是减半）减小为一个点，当前中间位置旁边的索引。

例如，假设您有一个数组tab [i] = i用于所有索引，并且所有值都在0到99之间。我们寻找51，第一个中位数是50，因此普通二进制搜索在最坏的情况下进行命中率（log2（100））。通过附加测试，我们测试了50个，并将搜索间隔减少到50个，因此分两步完成（但添加了测试）。

在最坏的情况下，当间隔为3而不是2时，我们似乎得出结论，因此进行log2（n）-1测试。

在代码中，这样会产生类似（此处使用Java）的调用，其中lo为0，array-1的长度为hi，以搜索整个数组：

// This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearchGT(int[] array, int value, int lo, int hi) {
        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }
成为

    static int binarySearch(int[] array, int value, int lo, int hi) {
        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                if (hi != mid && midVal == value -1) {
                    hi = mid + 1;
                } 
                lo = mid + 1;
            } else if (midVal > value) {
                if (lo != mid && midVal == value + 1) {
                    lo = mid - 1;                       
                }
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }
我的推理在认为在这种特定的离散/非重复输入情况下应该（总是）比常规二进制搜索更好（这是正确的吗？我确实看到我有一个额外的分支和两个布尔测试，其中包括一个额外的测试，但是仍然有大量输入，您能否展示这种策略显然最糟糕的情况？

有人知道文献中提到过类似的想法吗？

我正在考虑以下问题，给定大小为n的排序数组，其中包含没有重复的整数，我们可以比使用以下属性的普通二进制搜索更好：a）没有...

Answer 1

因为您不能保证在数组中将有一个值与要搜索的内容相邻，

在最坏的情况下