algorithm - 在数组中求偶数

我唯一能想到的就是进行线性搜索，并在到达数组末尾或找到偶数后停止。有人可以告诉我更好的方法吗？

最佳答案

您可以改为执行二进制搜索。编写一个执行以下操作的函数:

以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 stop，则没有更多可查找的内容。否则，打印输出，将其从数组中删除，并重复进行最多e试用。

二进制搜索算法将log(n)调用带给isEven，并且您必须最多运行e一次，因此，总共有e log(n)调用给isEven。

因此，无论何时使用e log(n) < n，您都希望采用这种方法，否则请使用线性搜索，该搜索会将n调用带给isEven。