Проверьте, присутствует ли элемент в массиве, используя не более пола (N/2) + 2 сравнения

Учитывая массив A[] размера N и целое число X , задача состоит в том, чтобы проверить, существует ли X в A[] с не более чем floor(N/2) + 2 сравнениями.
Примечание. Для любого индекса i (i < N) или (A[i] == X) рассматриваются как отдельные сравнения.

Примеры:

Input: A[] = {-3, 5, 11, 3, 100, 2, 88, 22, 7, 900, 23, 4, 1}, X = 88
Output: Yes 8
Explanation: X = 88 exists in the given array, A[] and is detected with 8 comparisons.

Input: A[]= {-3, 5, 11, 3, 100, 2, 88, 22, 7, 900, 23, 4, 1}, X = 6
Output: No
Explanation: X = 6 doesn’t exist in the given array, A[].

Подход: выполните шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, T как 1 , чтобы сохранить произведение всех элементов массива – X , т.е. (A[i] – X)
• Инициализируйте переменную, скажем, сравнения как 0 , чтобы сохранить необходимое количество сравнений.
• Инициализируйте указатель i как 0 для обхода массива.
• Если значение N нечетное, увеличьте сравнение на 1, потому что проверяется четность N, и обновите T до T * (A[0] – X) и i до 1 .
• Следовательно, количество элементов в диапазоне [i, N – 1], т.е. N – i , всегда четно.
• Перейдите массив A[] в диапазоне [i, N-1] и выполните следующие шаги:
  • Обновите значение T до T * (A[i] – X) * (A[i + 1] – X) .
  • Обновите i до i + 2 и увеличьте сравнение на 1 , поскольку проверяется условие i < N.
• Если значение T равно 0 , увеличьте сравнение на 1 , потому что сравнивается равенство T. Следовательно, X существует в A[] и выведите «Да» и количество сравнений .
• В противном случае в качестве результата выведите «Нет» .
• Алгоритм гарантирует, что количество сравнений ≤ floor(N / 2) + 2 .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)