Given an array of length n containing at most e even numbers and a function isEven that returns true if the input is even and false otherwise, write a function that prints all the even numbers in the array using the fewest number of calls to isEven.
我唯一能想到的就是进行线性搜索,并在到达数组末尾或找到 e 个偶数后停止。有人可以告诉我更好的方法吗?
最佳答案
您可以改用二进制搜索。编写执行以下操作的函数:
- 从
A = array
开始和n = length(A)
. - 同时
n>1
- 设置
L = [A[0],A[1],...,A[k-1]]
和R = [A[k],A[k+1],...,A[n-1]]
其中k = floor(n/2)
- 如果
isEven(product of elements of L)
, 然后设置A=L
和n = k
, - 否则设置
A=R
和n = n-k
.
- 设置
- 如果
isEven(A[0])
, 返回A[0]
, - 否则返回
-1
.
运行 for
最多有 e
的循环迭代。每次运行上面的算法寻找一个偶数,如果输出是-1
停下来,再也找不到了。否则,打印输出,将其从数组中删除,并最多迭代 e
试验。
二分查找算法取log(n)
调用 isEven
, 你最多必须运行它 e
次,所以一共有e log(n)
调用 isEven
.
因此,无论何时e log(n) < n
,您都希望采用这种方法。 ,否则使用线性搜索,它需要 n
调用 isEven
.
关于algorithm - 查找数组中的偶数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8582959/