什么是二元插值搜索？

Question

我了解什么是二进制搜索以及插值搜索。

我必须回答一个问题，让我在一个句子中解释什么是二进制插值搜索（bis）。这不是二进制搜索和插值两种不同的搜索吗？我已经搜索了很多，找不到这种搜索。我想念什么？

Answer 1

我不确定二进制插值搜索到底执行什么操作，但是，二进制插值排序已应用于插入排序。例如，给定一个元素，插入到已排序的数组中并同时保持其排序。如果我们直接将它与每个 emelemt 进行比较以找到正确的插入位置，时间复杂度将是 O(n)，现在它已经排序了，可以应用二分查找来处理这种情况，时间复杂度为 O(logn)，如下我们都知道。