在数组中查找偶数

Question

给定一个长度为n的数组,其中包含最多e个偶数,并且函数isEven如果输入为偶数则返回true,否则为false,编写一个函数,使用对isEven的最少调用次数打印数组中的所有偶数.

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

Answer 1

您可以改为进行二分查找.编写执行以下操作的函数:

• 从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.