请考虑以下数据:
ARR=[2，3，5，7，11，13，17，19]
N=100
给定的输出应为0，因为n%2=0且arr[0]=2.
因为数组是排序的，所以我想利用这一点，设计一种复杂度小于O(N)的算法，通过迭代整个数组并首先找到i，使n%arr[i]=0.
我立刻想到了使用改进的二进制搜索，其复杂性与常规二进制搜索(O(Logn))相同，后者的作用与常规二进制搜索相同，后者在每次迭代中将搜索间隔一分为二，但略有修改.下面是我使用的实现:
public int SmallestFactorIndex(int n)
{
int left = 0;
int right = max;
int index = -1;
while (left <= right)
{
int middle = (right - left) / 2 + left;
int middleValue = sieve[middle];
if (n % middleValue == 0)
{
index = middle;
right = middle - 1;
}
else if (middleValue < n)
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
return index;
}
Max表示数组的长度-1，而Sieve是素数的排序array. 除了二进制搜索之外，如果当前数字除以n，我不会立即返回该索引，而是通过将右边界移到中间来继续搜索比当前数字更小的数字.所有其他部分的工作方式基本相同. 我不认为我可以利用数组只由质数组成的事实，但我可能错了.