Пусть дан упорядоченный по неубыванию массив целых или действительных чисел a1<=a2<=...<=an и пусть дано некоторое число b (соответственно целое или действительное), для которого нужно найти такое место среди чисел a1,...,an , чтобы после вставки числа b на это место упорядоченность не нарушилась. Если вследствие равенства между собой некоторых элементов массива число b можно вставлять на разные места, то требуется определить ближайшее к началу массива место. Эта задача называется поиском места элемента. Для b имеется n+1 возможность: b<=a1, a1<b<=an, an<b, и решением задачи поиска элемента b будет соответственно одно из чисел 1,...,n+1. Для решения задачи полезен алгоритм, который называется алгоритмом деления пополам: взять первоначально 1 и n+1 в качестве границ поиска места элемента; далее, до тех пор пока границы не совпадут, шаг за шагом сдвигать эти границы следующим образом: сравнить b с a, где s - целая часть среднего арифметического границ; если b>a - заменить прежнюю нижнюю границу на s+1, а верхнюю оставить без изменения, иначе оставить без изменения нижнюю границу, а верхнюю заменить на s; когда границы совпадут, став равными некоторому числу t, выполнение вышеописанного алгоритма закончится с результатом t. (Число сравнений, требуемых этим алгоритмом, не превосходит [log2(n+1)]+1 ).
Само задание:
a) даны действительные числа a1,...,an (причем упорядочены по возрастанию a1<=a2<=...<=an) и b1,...,bm. Получить натуральные числа k1,...,km такие, kj- решение задачи поиска места bj среди a1,...,an (i=1,...,m). Применить алгоритм деления пополам
