Завдання 13 Дедлайн 21 грудня

Рекурсивний виклик функцій здебільшого демонструють на простих алгоритмах: послідовність Фібоначчі чи факторіал. Більш практичне застосування рекурсії — обхід графів та бінарний пошук. Останній — це дуже швидкий пошук даних у відсортованому масиві. Якщо звичайний лінійний пошук працює за O(N), а це 1000 порівнянь для 1000 елементів, то бінарний — за O(log2N), а це всього 10 порівнянь для 1000 елементів.
Нижче наведено код програми, яка використовує бінарний пошук. Потрібно дописати реалізацію binary_search() згідно коментарів в тілі функції, використовуючи рекурсію.

#include <iostream>

int binary_search(int* arr, int first, int last, int value) {
   // Якщо індекс першого елемента (first) менший за індекс останнього (last),
   // то value в цілому масиві немає - повернути -1.
   
   // Обчислити індекс елемента посередині - index. Він ділить поточний
   // інтервал [first, last] на дві половини:
   //  * [first, index - 1]
   //  * [index + 1, last]
   
   // Якщо елемент arr[index] і шукане значення співпали - повернути
   // обчислений індекс.
   
   // Якщо елемент посередині більший за value, то знову викликати і повернути
   // результат роботи binary_search() для першої половини інтервалу,
   // а інакше - для другої.
   
}

int main() {
   // Зчитати розмір масиву.
   int size;
   std::cout << "Enter size: ";
   std::cin >> size;
   // Зчитати масив.
   std::cout << "Enter array: ";
   int* arr = new int[size];
   for (int i = 0; i < size; ++i) std::cin >> arr[i];
   // Зчитати число, яке потрібно знайти.
   int value;
   std::cout << "Enter value: ";
   std::cin >> value;
   // Вивести індекс числа в масиві і деалокувати масив.
   std::cout << "Value index: "
             << binary_search(arr, 0, size - 1, value)
             << std::endl;
   delete[] arr;
   return 0;
}

Приклади роботи
1. Елемент менший за всі інші.

Enter size: 6
Enter array: 1 3 5 7 9 10
Enter value: 0
Value index: -1

2. Елемент менший за всі інші.

Enter size: 6
Enter array: 1 3 5 7 9 10
Enter value: 11
Value index: -1

3. Елемент в проміжку, але відсутній.

Enter size: 6
Enter array: 1 3 5 7 9 10
Enter value: 4
Value index: -1

4. Перший елемент.

Enter size: 6
Enter array: 1 3 5 7 9 10
Enter value: 1
Value index: 0

5. Останній елемент.

Enter size: 6
Enter array: 1 3 5 7 9 10
Enter value: 10
Value index: 5

6. Звичайний елемент.

Enter size: 6
Enter array: 1 3 5 7 9 10
Enter value: 9
Value index: 4

Відповідь:

#include <iostream>

int binary_search(int* arr, int first, int last, int value) {
   // Якщо індекс першого елемента (first) менший за індекс останнього (last),
   // то value в цілому масиві немає - повернути -1.
   if (last < first) return -1;
   // Обчислити індекс елемента посередині - index. Він ділить поточний
   // інтервал [first, last] на дві половини:
   //  * [first, index - 1]
   //  * [index + 1, last]
   int index = first + (last - first) / 2;
   // Якщо елемент arr[index] і шукане значення співпали - повернути
   // обчислений індекс.
   if (arr[index] == value) return index;
   // Якщо елемент посередині більший за value, то знову викликати і повернути
   // результат роботи binary_search() для першої половини інтервалу,
   // а інакше - для другої.
   return (arr[index] > value) ? binary_search(arr, first, index - 1, value)
                               : binary_search(arr, index + 1, last, value);
}

int main() {
   // Зчитати розмір масиву.
   int size;
   std::cout << "Enter size: ";
   std::cin >> size;
   // Зчитати масив.
   std::cout << "Enter array: ";
   int* arr = new int[size];
   for (int i = 0; i < size; ++i) std::cin >> arr[i];
   // Зчитати число, яке потрібно знайти.
   int value;
   std::cout << "Enter value: ";
   std::cin >> value;
   // Вивести індекс числа в масиві і деалокувати масив.
   std::cout << "Value index: "
             << binary_search(arr, 0, size - 1, value)
             << std::endl;
   delete[] arr;
   return 0;
}