Дан упорядоченный по неубыванию массив чисел A1,A2,...,An и дано некоторое действительное число B, для которого нужно найти такое место среди чисел A1,A2,...,An, чтобы после вставки B на это место упорядоченность не нарушилась. Эта задача называется задачей поиска места элемента: пусть даны числа A1,A2,...,An, B1,B2,...,Bm, получить числа K1,K2,...,Km, такие, что Ki - решение задачи поиска места Bi в массиве A. Применить алгоритм деления пополам.
Алгоритм:
1. Задаем массив чисел.
2. Получаем некоторое действительное число B, чье место в массиве нам предстоит найти.
3.1 Если B меньше первого элемента массива, значит он должен стоять на пером месте.
3.2 Если B больше последнего элемента массива, ставим его в конец.
3.3 Для остальных случаев применяем алгоритм деления пополам (BinatySearch) и выводим возможные позиции в массиве.
Примечание: массив генерируется случайным образом из действительных чисел.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
double Array[MAX];
double D;
// Реализация алгоритма деления пополам.
void BinarySearch (int *a, int *b)
{
int i;
extern double D;
extern double Array[];
int toLeft, toRight;
toLeft=0;
toRight=MAX-1;
*a=*b=0;
while (1)
{
i=(toLeft+toRight) / 2;
if (D < Array[i])
{
toRight= i-1;
*b = i;
}
else if (D > Array[i])
{
toLeft= i+1;
*a=i;
}
if (*a>0 && *b>0 && (*b-*a)<2)
return;
if (toLeft > toRight)
return;
}
return;
}
int main ()
{
int i;
int a,b;
extern double Array[];
extern double D;
Array[0]=10; // for example
for (i=1; i<MAX; i++) {
Array[i]=Array[i-1] + (rand() % 4);
//printf("%i: %f\n",i,Array[i]); //for debugging
}
printf("Please, write D: ");
scanf("%lf",&D);
if (D < Array[0]) printf("D can go first.\n");
else if (D > Array[MAX-1]) printf("D should be at the end.\n");
else {
BinarySearch(&a,&b);
printf("D should can be on: ");
for (i=a; i<=b; i++)
if (i!=b) printf("%d, ",i);
else printf("%d",i);
printf("\n");
}
return 0;
}
Ключевые слова:
алгоритм деления пополам, поиск места в массиве действительных чисел, порядок чисел в массиве
