Пусть дан массив a длины n, элементы которого нестрого возрастают, т.е. соседние элементы могут быть равными. Рассмотрим фрагмент программы бинарного поиска элемента x в массиве a длины n, где после отбрасывания особых ситуаций рассматривается основной случай: . . . // Утверждение: a[0] <= x && x < a[n-1] int beg = 0; int end = n-1; while (end-beg > 1) { // Инвариант: a[beg] <= x && x < a[end] int c = (beg + end) / 2; if (a[c] <= x) { beg = c; } else { end = c; } } if (a[beg] == x) { *idx = beg; } else { *idx = end; } . . . Пусть значение x содержится в массиве в нескольких экземплярах. Индекс какого элемента массива a будет записан в переменную *idx?

Правильный ответ:

• # Пусть f(x) - гладкая функция, заданная на отрезке [a, b], производная которой по абсолютной величине не превышает некоторой константы. Для приближенного вычисления интеграла от этой функции мы применяем формулу прямоугольников, разбивая отрезок [a, b] на n равных частей. Какова точность вычисления интеграла в зависимости от n?
• # Сколько всего простых чисел в диапазоне от 100 до 110?
• # Какие переменные располагаются в языке C/C++ в статической памяти?
• # В каком порядке фактические аргументы функции помещаются в стек при ее вызове в языке C/C++?
• # Алгоритм сортировки называется стабильным, если он сохраняет взаимный порядок равных элементов. (Такое определение имеет смысл при сортировке массива записей, состоящих из нескольких полей, которые сравниваются лишь по значению одного конкретного поля - например, записи о людях сортируются по их именам, при этом могут быть однофамильцы.) Является ли алгоритм быстрой сортировки стабильным?