1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| #include<locale.h>
#include<stdio.h>
#include<iostream>
#include<time.h>
#include<algorithm>
#include<vector>
using namespace std;
void block_search_ord(int*, int, int);
void BinarniySearch(int*, int, int);
int l=0;
int main()
{
for (;;)
{
setlocale(LC_ALL, "rus");
int mass[1000], a, b, x, size, n;
printf("Введите размерность массива: ");
scanf_s("%d", &size);
printf("Введите диапазон чисел массива от a до b (0 - 1000): ");
scanf_s("%d%d", &a, &b);
printf("Сгенерированный массив: ");
srand(time(NULL));
for (short i = 0; i < size; i++)//заполнение массива случайными числами
{
mass[i] = a + rand() % (b - a);
cout << mass[i] << " ";
}
for (int j = 0; j < size - 1; j++)
{
for (int i = 0; i < size - 1; i++)
{
if (mass[i] > mass[i + 1])
{
a = mass[i];
mass[i] = mass[i + 1];
mass[i + 1] = a;
}
}
}
cout << "\nУпорядоченный массив: ";
for (short i = 0; i < size; i++)
{
cout << mass[i]<<" ";
}
cout << endl;
printf("\nВведите искомый элемент: ");
cin >> x;
printf("Выберите алгоритм поиска: \n1 - m-блочный поиск\n2 - Бинарный поиск\n3 - поиск с помощью встроенных функций С++: ");
scanf_s("%d", &n);
if (n == 1)
{
block_search_ord(mass, size, x);//m-блочный поиск
}
else if (n == 2)
{
barrier(mass, size, x);//Бинарный поиск
}
else if (n == 3)//поиск с помощью встроенной функции find()
{
vector<int> v(mass, mass + size);
int i = find(v.begin(), v.end(), x) - v.begin();
if (i < size)
cout << "Элемент " << x << " находится под индексом: " << i << endl;
else cout << "Элемент " << a << " не найден в данном массиве " << endl;
}
}
return 0;
}
void block_search_ord(int* arr, int n, int a)
{
int i = 0, m=0, l, sr = 0;
m=n/sqrt(n);
for (short i = m-1; i < n;)
{
l=i;
sr++;
if(a<arr[i]){
l= i - (m+1);
break;
}
else if(a==arr[i])
{
cout << "Элемент "<<a<<" находится под индексом: " << i<<endl
<< "Количество сравнений = "<< sr+1<< endl;
}
i=i+m;
}
int c=l+m;
for(l;l<c;l++)
{
sr++;
if (l > (n - 1))
{
cout << "Элемент " << a << " не найден в данном массиве "<<endl;
break;
}
if(a==arr[l])
{
break;
}
}
if (l<(n-1)) cout << "Элемент "<<a<<" находится под индексом: " << l<<endl
<< "Количество сравнений = "<< sr+1<< endl;
}
void barrier(int *Arr, int size, int key)
{
setlocale(LC_ALL,"Russian");
int j = 0;
int counter = 0;
Arr[size] = key;
while(true)
{
counter++;
if(Arr[j] == key)
{
break;
}
j++;
}
if (j>=size)
{
cout <<"Нет ключа! " << key << "\nСравнений:" << counter << endl;
cout << "--------------------" << endl;
}
else
{
cout <<"Ключ найден! " << key << "\nСравнений:" << counter << endl;
cout << "--------------------" << endl;
}
} |
(
Сообщение от Quentyn
