确定排序数组中的任何数字是否为x的倍数的最快算法是什么? [英] What is the fastest algorithm to determine if any number in a sorted array is multiple of `x`?

问题描述

给出一个正整数x和一个排序后的正整数数组A

Given an positive integer x and a sorted positive integer array A

是否有比O(N)更快的算法来确定A中的任何元素是否为x的倍数? A中没有否定元素.

Is there any algorithm faster than O(N) to determine if any element in A is a multiple of x? There are no negative elements in A.

天真循环A是我唯一的主意，我不知道是否有任何办法利用A进行排序以加快速度的事实.

Naive looping A once is my only idea so far, I do not know if there is any way to make use of the fact that A is sorted to speed it up.

推荐答案

这似乎很大程度上取决于x的大小和A中元素的数量，尤其是在A之内.

This seems to depend very much on the size of x and the number of elements within A, and particularly the number of candidate multiples of x within A.

对A中的特定数字进行二进制搜索需要O(log(n))时间(n是A中的元素数)，因此如果在A之间存在k可能的x倍数A的第一个和最后一个元素，将需要O(k * log(N))进行全部检查.如果该数字小于n，则可以使用此算法，否则只需进行线性搜索即可.

Binary-searching a specific number within A takes O(log(n)) time (n being the number of elements within A), so if there are k possible multiples of x between the first and the last element of A, it will take O(k * log(N)) to check them all. If that number is smaller than n, you can use this algorithm, otherwise just do a linear search.

(此外，上述算法可能还有一些小的优化.例如，一旦选中x*i(但未找到它)，则可以使用x*i应该作为下限的位置搜索x*(i+1)而不是数组的第一个元素.)

(Also, there are probably a few small optimizations to above algorithm. E.g., once you checked x*i (and did not find it), you can use the position where x*i should have been as the lower bound when searching for x*(i+1) instead of the very first element of the array.)

这篇关于确定排序数组中的任何数字是否为x的倍数的最快算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！