有效搜索已排序的数值
我有一个int[]数组，其中包含具有以下属性的值：
- 他们排序
- 它们是独一无二的 （没有重复）
- 它们在已知范围内 [0..MAX]
- MAX通常比arrays的长度大很多（例如10-100x）
- 有时数字在整个范围内均匀分布，但在其他时间有很长的连续数字序列。 我估计这两种情况之间约为50/50。
鉴于此列表，我想有效地找到数组中特定值的索引（或者如果该值不存在，则找到下一个更高的值）。
我已经实现了一个带间隔二分的直接二分搜索 ，它运行得相当好，但我怀疑数据的性质/分布可以被利用来更快地收敛到解决方案。
我对优化平均案例搜索时间感兴趣，但重要的是最坏的情况永远不会比O（log n）差，因为数组有时非常大。
问题：在普通情况下，有可能比纯二进制搜索做得更好吗？
编辑 （澄清其他问题/意见）
- O（log n）中的常数绝对重要。 事实上，假设比O（log n）更好的算法复杂度是不可能的，常量可能是唯一重要的…..
- 它通常是一次性搜索，因此虽然预处理是可能的，但它可能不值得。
让我们在这里命名区间x ，并命名搜索到的数字。
由于您希望值均匀分布，因此可以使用插值搜索。 这类似于二分搜索，但是在start + ((z - x[start]) * (end - start)) / (x[end] - x[start])拆分索引范围。
要获得O(log n)的运行时间，您必须将插值搜索与二分搜索相结合（从二进制搜索开始步骤并从插值搜索交替步进）：
public int search(int[] values, int z) { int start = 0; int end = values.length-1; if (values[0] == z) return 0; else if (values[end] == z) { return end; } boolean interpolation = true; while (start < end) { int mid; if (interpolation) { mid = start + ((z - values[start]) * (end - start)) / (values[end] - values[start]); } else { mid = (end-start) / 2; } int v = values[mid]; if (v == z) return mid; else if (v > z) end = mid; else start = mid; interpolation = !interpolation; } return -1; }
由于while循环的每第二次迭代在二进制搜索中执行一步，因此它最多使用二进制搜索将使用的迭代次数的两倍（ O(log n) ）。 由于每个第二步都是插值搜索的一步，因此如果输入具有所需的属性，则算法应该快速减小间卷大小。
这是在评论中，应该是一个答案。 这是一项共同的努力，所以我将它作为一个CW答案：
您可能想要查看插值搜索 。 在最坏的情况下，它们可能比O(log n)更差，所以如果这是一个很难的要求，这将不适用。 但是如果你的插值是不错的，根据数据分布，插值搜索可以击败直接二进制。
要知道，您必须使用合理智能的插值算法实现插值搜索，然后通过两者运行几个代表性数据集，以查看插值或二进制是否更适合。 我认为它是两者中的一个，但我并不是真正的尖端搜索算法。
如果int []是
- 分类
- 有独特的价值观
- 你知道范围（提前）
而不是搜索为什么不在其索引处保存值。
假设数字是243而不是保存int [243] = 243中的值。
这样搜索将变得简单快捷。 唯一剩下的就是找出下一个更高的价值。
我有一个解决方案。
你说arrays可以
1）数字在整个范围内均匀分布
2）有很长的连续数字序列。
所以，首先我们开始一个简单的测试，以确定它是type1还是type2。
要测试类型1，
lenght = array.length;
range = array [length-1] – array [0];
现在考虑数组的值
{长度（1/5），长度（2/5），长度（3/5），长度（4/5）}，
如果数组分布是类型1，那么我们大致知道数组[i]的值必须是什么，所以我们检查在4个位置以上的位置是否接近已知值，如果它是相等的分布。
如果它们接近，那么它的分布相等，所以我们可以很容易地找到数组中的任何元素。如果我们找不到基于上述方法的元素，我们认为它是类型2。
如果上面的测试失败那么它是类型2 ，这意味着在数组中几乎没有存在连续数字的长序列的地方。
所以，我们用二分法搜索来解决它。解释如下
*我们首先在数组的中间搜索，（比如说长度为2，索引为i）
left = 0，right = length;
开始 ：
I =（左+右）/ 2;
情况a.1 ：我们的搜索号大于数组[i]
左= I;
*现在我们检查那个位置是否存在任何长的连续序列，即
array [i]，array [i + 1]，array [i + 2]是连续的int。
案例a.1.1 :(如果它们是连续的），
因为它们是连续的，并且序列可能很长，所以我们根据搜索整数值直接搜索特定索引。
例如，如果我们的搜索int是10，序列是5,6,7,8,9,10,11 15,100,103，
和array [i] = 5，然后我们直接搜索数组[i + 10-5]，
如果我们找到我们的搜索int，则返回它，否则只从case a.2继续[因为它显然会小于它]通过设置为right
右=（arrays[I + 10-5]）
情况a.1.2，如果它们不是连续的
从BEGIN继续;
情况a.2：我们的搜索号小于array [i]，
*案例a.2与a.1完全相似
*同样检查是否有任何后序，即数组[i-2]，数组[i-1]，数组[i]是顺序的，
如果它们是连续的序列，请像我们在a.1.1中那样搜索回精确值
如果它们不连续，则重复类似于案例a.1.2。
情况a.3 ，这是我们的搜索int，
然后归还它。
希望这可以帮助