w jakich przypadkach zlozonosc funkcji search() jest lepsza niz O(n)
# include <iostream>
using namespace std;
struct range;
struct range {
double begin;
double end;
range *left;
range *right;
range (double a, double b) {
begin = a;
end = b;
left = NULL;
right = NULL;
}
};
range *rangePointer;
bool add (double a, double b, range *&r = rangePointer) {
if (r == NULL) {
r = new range( a, b );
return true;
}
if (r->begin > b) {
return add( a, b, r->left );
}
if (r->end < a) {
return add( a, b, r->right );
}
return false;
}
void search (double f, range *&r = rangePointer) {
if (r == NULL) {
cout << "liczba " << f << " nie nalezy do zadnego z przedzialow" << endl;
return;
}
if (r->begin > f) {
return search(f, r->left);
}
if (r->end < f) {
return search(f, r->right);
}
cout << "liczba " << f << " nalezy do ( " << r->begin << ", " << r->end << " )" << endl;
return;
}
int main () {
bool odp = true;
int rep = 0;
double begin = 0, end = 0, number = 0;
while (odp) {
printf("\n\nPodaj: ");
printf("\n1) aby dodac nowy przydzial");
printf("\n2) aby wyszukac liczbe w przedziale");
printf("\n3) aby zakonczyc program\n");
scanf("%d",&rep);
switch (rep) {
case 1:
printf("\nPodaj odpowiednio poczatek i koniec przedzialu: \n");
scanf("%d",&begin);scanf("%d",&end);
add(begin,end);
break;
case 2:
printf("\nPodaj liczbe aby wyszukac przedzial w ktorym sie znajduje: ");
scanf("%d",&number);
search(number);
break;
case 3:
odp = false;
}
}
system("pause");
return 0;
}