我有一个实际值的排序(升序)数组,称之为(可能重复).我希望在给定一系列值[x,y]的情况下,找到索引j存在的所有值(i)的索引,使得:j> i和x <= a [j] -a [i] <=或者简单地说,找到在给定范围内存在"前向差异"的值.
输出是一个长度为a.Length的布尔数组.由于数组是对所有前向差异进行排序,因此x和y为正.
我设法做的最好的是从每个索引开始查看它前面的子阵列并执行二进制搜索x + a [i]并检查是否[j] <= y + a [i].我认为这是O(n log n).有更好的方法吗？或者我可以做些什么来加快速度.
我应该注意到,最终我想在同一个数组a上搜索许多这样的范围[x,y],但是范围的数量远小于数组的长度(小4-6个数量级) - 因此我更关心搜索的复杂性.
例:
a= 0, 1, 46, 100, 185, 216, 285
范围x,y = [99,101]应该返回:
[true, true, false, false, true, false, false]
仅对于值0,1和185在该范围内具有前向差异.
内存中的代码可能有一些错误:
int bin_search_closesmaller(int arr[], int key, int low, int high)
{
if (low > high) return high;
int mid = (high - low)/2;
if (arr[mid] > key) return bin_search_closesmaller(arr, key, low, mid - 1);
if (arr[mid] < …