algorithm - 查找数组中的偶数

Question

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 个偶数后停止。有人可以告诉我更好的方法吗？

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 .