在一个阵列查找偶数 [英] Finding even numbers in an array

问题描述

由于长度为n的含大多数电子偶数和数组   功能ISEVEN返回true，如果输入的是，即使假   否则，编写打印所有的偶数的函数   阵列使用尽可能少的调用ISEVEN的。

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.

我能想到的唯一的事情是做线性搜索，并停止后，我打了数组的末尾或者发现Ë偶数。是否有人可以告诉我一个更好的办法？

The only thing I could think was to do a linear search and stop after I hit the end of the array or found e even numbers. Can someone please tell me a better way?

推荐答案

您可以做一个二进制搜索来代替。编写一个函数，执行以下操作：

You can do a binary search instead. Write a function that does the following:

• 以 A =阵列和 N =长度（A）。
• 在 N'GT; 1
  • 设置 L = [A [0]，A [1]，...，A [K-1] 和 R = [A [K]，A [K + 1]，...，A [N-1] ，其中 K =地板（N / 2）
  • 如果 ISEVEN（L元素的产品），然后设置 A = L 和 N =氏/ code>，
  • 否则设置 A = R 和 N = NK 。
  • Start with A = array and n = length(A).
  • While n>1
    • Set L = [A[0],A[1],...,A[k-1]] and R = [A[k],A[k+1],...,A[n-1]] where k = floor(n/2)
    • If isEven(product of elements of L), then set A=L and n = k,
    • Otherwise set A=R and n = n-k.

    运行为循环，将有至多电子迭代。每次运行上述算法找到一个偶数，如果输出是 1 停止，有没有更多的查找。否则，打印输出，从阵列中删除，并循环在大多数电子试验。

    Run a for loop that will have at most e iterations. Each time run the algorithm above to find an even number, if the output is -1 stop, there are no more to find. Otherwise, print the output, remove it from the array, and iterate for at most e trials.

    的二进制搜索算法以的log（n）调用 ISEVEN ，你必须在最运行电子次，所以总共有电子的log（n）调用是ISEVEN 。

    The binary search algorithm takes log(n) calls to isEven, and you must run it at most e times, so there are a total of e log(n) calls to isEven.

    因此​​要采取这种方法，只要电子的log（n）＆LT; ñ，否则使用线性搜索，它接受 N 调用 ISEVEN 。

    Therefore you want to take this approach whenever e log(n) < n, otherwise use the linear search, which takes n calls to isEven.

    这篇关于在一个阵列查找偶数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！