Напишите функцию, которая находит, сколько раз входное число встречается в одномерном массиве с помощью двоичного поиска.
#include <iostream> #include <algorithm> using namespace std; int binary_search(int arr[], int num, int start, int end) { if (start > end) { return 0; } int mid = (start + end) / 2; if (arr[mid] == num) { return 1 + binary_search(arr, num, start, mid - 1) + binary_search(arr, num, mid + 1, end); } else if (arr[mid] > num) { return binary_search(arr, num, start, mid - 1); } else { return binary_search(arr, num, mid + 1, end); } } int main() { // Пример использования функции: int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int num = 5; int num_count = binary_search(arr, num, 0, 9); cout << "Число " << num << " встречается в массиве " << num_count << " раз(а)." << endl; return 0; } C #include <iostream> #include <algorithm> using namespace std; int binary_search(int arr[], int num, int start, int end) { if (start > end) { return 0; } int mid = (start + end) / 2; if (arr[mid] == num) { return 1 + binary_search(arr, num, start, mid - 1) + binary_search(arr, num, mid + 1, end); } else if (arr[mid] > num) { return binary_search(arr, num, start, mid - 1); } else { return binary_search(arr, num, mid + 1, end); } } int main() { // Пример использования функции: int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int num = 5; int num_count = binary_search(arr, num, 0, 9); cout << "Число " << num << " встречается в массиве " << num_count << " раз(а)." << endl; return 0; }
тоже нейронка #include <iostream> #include <algorithm> int binary_search(int arr[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } int count_occurrences(int arr[], int n, int target) { int count = 0; int index = binary_search(arr, n, target); while (index != -1) { count++; index = binary_search(arr, n, target, index + 1); } return count; } int main() { int arr[] = {1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9}; int target = 5; int count = count_occurrences(arr, 11, target); std::cout << "Number of occurrences of " << target << ": " << count << std::endl; return 0; } C #include <iostream> #include <algorithm> int binary_search(int arr[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } int count_occurrences(int arr[], int n, int target) { int count = 0; int index = binary_search(arr, n, target); while (index != -1) { count++; index = binary_search(arr, n, target, index + 1); } return count; } int main() { int arr[] = {1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9}; int target = 5; int count = count_occurrences(arr, 11, target); std::cout << "Number of occurrences of " << target << ": " << count << std::endl; return 0; }
Считать сколько раз число встречается в одномерном массиве с помощью двоичного поиска - если массив не отсортирован то это наверно самый идиотский вариант решения этой задачи