Нахождение четных чисел в массиве

Question

Учитывая массив длины n, содержащий не более e четных чисел, и функцию isEven, которая возвращает значение true, если входные данные являются четными, и ложь в противном случае, напишите функцию, которая печатает все четные числа в массиве, используя наименьшее числовызовов 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 stop, больше ничего не найдено.В противном случае выведите выходные данные, удалите их из массива и выполните итерацию не более e испытаний.

Алгоритм двоичного поиска принимает log(n) вызовов isEven, и вы должны запустить его максимум e раза, то есть всего e log(n) вызовов isEven.

Поэтому вы хотите использовать этот подход всякий раз, когда e log(n) < n, в противном случае используйте линейный поиск, который принимает n вызововisEven.