确定排序数组中的任何数字是否为x的倍数的最快算法是什么？
给定一个正整数x和一个排序的正整数数组A
有没有比O(N)确定其中任何元素A是否为的倍数更快的算法x？中没有负面因素A。
A到目前为止，天真循环是我唯一的想法，我不知道是否有任何方法可以利用A经过分类的事实来加快循环速度。
回答：
这似乎在很大程度上取决于大小x和内部元件的数量A，以及候选倍数的特别的数量x之内A。
对内的特定数字进行二进制搜索A需要O（log（n））时间（n是中的元素数A），因此，如果的第一个元素和最后一个元素之间k可能存在倍数，则需要检查所有x元素。如果该数字小于，则可以使用此算法，否则只需进行线性搜索即可。A``O(k
* log(N))``n
（此外，上述算法可能还有一些小的优化。例如，一旦检查x*i（但未找到），则可以使用搜索时本x*i应位于的位置作为下限，x*(i+1)而不是使用数组。）
以上是 确定排序数组中的任何数字是否为x的倍数的最快算法是什么？ 的全部内容， 来源链接： utcz.com/qa/402394.html
