Занятие №5 Класс алгоритмических методов «разделяй и властвуй»

Программная реализация алгоритма:
#include
#include
#include
using namespace std;
int bsearch(const vector &arr, int l, int r, int q)
{
while (l <= r)
{
int mid = l + (r-l)/2;
if (arr[mid] == q) return mid;
if (q < arr[mid]) { r = mid - 1; }
else { l = mid + 1; }
}
return -1; // не нашли
}
int main()
{
int query = 10;
int arr[] = {2, 4, 6, 8, 10, 12};
int N = sizeof(arr) / sizeof(arr[0]);
vector v(arr, arr + N);
// Сортируем входной массив
sort(v.begin(), v.end());
int idx;
idx = bsearch(v, 0, v.size(), query);
if (idx != -1)
cout << "бинарный поиск: нашли по индексу " << idx;
else
cout << "бинарный поиск: не нашли";
return 0;
}

Код выводит следующее:

бинарный поиск: нашли по индексу 4

Если искомый элемент не найден, но мы хотим найти ближайший элемент меньше или больше запроса, то можно использовать функции STL lower_bound() и upper_bound().

Варианты заданий
1. В массиве целых чисел с помощью рекурсивной функции найти количество четных элементов.
2. В массиве целых чисел с помощью рекурсивной функции найти количество элементов массива, которые делятся на 5 и не делятся на 7.
3. В массиве целых чисел с помощью рекурсивной функции найти количество простых чисел.
4. В массиве целых чисел с помощью рекурсивной функции найти сумму
нечетных элементов.
5. Найти максимальный элемент целочисленного массива с помощью рекурсии.
6. Вычислить сумму только симметричных элементов массива с помощью рекурсии.
7. В массиве целых чисел с помощью рекурсивной функции найти сумму
таких элементов, которые состоят только из четных цифр.
8. В массиве целых чисел с помощью рекурсивной функции найти количество элементов, больших заданного числа A.
9. В массиве целых чисел с помощью рекурсии найти количество минимальных элементов.
10. В массиве целых чисел с помощью рекурсии найти сумму элементов
массива, расположенных в интервале (А, В).
11. Найти количество двузначных элементов массива с помощью рекурсии.
12. Найти минимальный элемент целочисленного массива с помощью рекурсии.
13. В массиве целых чисел с помощью рекурсии найти количество максимальных элементов.
14. Вычислить сумму только двузначных элементов массива с помощью
рекурсии.
15. В массиве целых чисел с помощью рекурсивной функции найти сумму элементов, заканчивающихся на 7.
16. В массиве целых чисел с помощью рекурсивной функции найти сумму всех элементов массива, которые одновременно делятся на 3 и на 5.
17. В массиве целых чисел с помощью рекурсивной функции найти количество элементов, начинающихся на 3.
Литература

1. 
   Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
   
2. 
   Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
   
3. 
   Ворожцов А.В., Винокуров Н.А. Лекции «Алгоритмы: построение, анализ и реализация на языке программирования Си». – М.: Издательство МФТИ, 2007.