Алгоритм бинарного поиска применяется в случае, когда необходимо осуществить поиск на больших массивах многократно. Написать асимптотику работы самого алгоритма O (log2 n).
Ссылка на код
https://onlinegdb.com/Erp7LDb1w
C/C++
Dev C++. Выдаёт ошибки( Помогите, пожадуйста, исправить
#include <iostream>
#include <set>
#include <vector>
#include <random>
#include <cmath>
#include <iomanip>
using namespace std;
vector<int> make_random_array(const size_t length) {
uniform_int_distribution<> uid(1, static_cast<int>(length << 1));
mt19937 gen{ random_device()() };
auto rand = [&](int& x) { x = uid(gen); };
set<int> tmp;
do tmp.emplace(uid(gen)); while (tmp.size() != length);
vector<int> box{ tmp.begin(), tmp.end() };
return box;
}
void show(const vector<int>& box) {
if (box.empty()) puts("Empty box!");
else {
const auto width = static_cast<streamsize>(log10(box.back())) + 2;
for (auto x : box) cout << x << ' ';
puts("");
}
}
// Алгоритм бинарного поиска
auto bin_search(const int key, vector<int>& box) {
auto low = box.begin();
auto high = box.end() - 1;
while (low <= high) {
auto pos = distance(low, high) >> 1;
auto mid = low + pos;
if (*mid < key) low = mid + 1;
else if (*mid > key) high = mid - 1;
else return mid;
}
return box.end();
}
int main() {
cout << "Length: ";
size_t length;
cin >> length;
auto box = make_random_array(length);
show(box);
auto pos = box.end();
while (true) {
cout << "Key: ";
int key;
cin >> key;
pos = bin_search(key, box);
if (pos != box.end()) puts("Value found!");
else puts("Value not found!");
}
}
#include <set>
#include <vector>
#include <random>
#include <cmath>
#include <iomanip>
using namespace std;
vector<int> make_random_array(const size_t length) {
uniform_int_distribution<> uid(1, static_cast<int>(length << 1));
mt19937 gen{ random_device()() };
auto rand = [&](int& x) { x = uid(gen); };
set<int> tmp;
do tmp.emplace(uid(gen)); while (tmp.size() != length);
vector<int> box{ tmp.begin(), tmp.end() };
return box;
}
void show(const vector<int>& box) {
if (box.empty()) puts("Empty box!");
else {
const auto width = static_cast<streamsize>(log10(box.back())) + 2;
for (auto x : box) cout << x << ' ';
puts("");
}
}
// Алгоритм бинарного поиска
auto bin_search(const int key, vector<int>& box) {
auto low = box.begin();
auto high = box.end() - 1;
while (low <= high) {
auto pos = distance(low, high) >> 1;
auto mid = low + pos;
if (*mid < key) low = mid + 1;
else if (*mid > key) high = mid - 1;
else return mid;
}
return box.end();
}
int main() {
cout << "Length: ";
size_t length;
cin >> length;
auto box = make_random_array(length);
show(box);
auto pos = box.end();
while (true) {
cout << "Key: ";
int key;
cin >> key;
pos = bin_search(key, box);
if (pos != box.end()) puts("Value found!");
else puts("Value not found!");
}
}
Ибрагим Федоров
Никола, спасибо большое, А можно подкоректировать что б в конце вот такое получилось?

Алгоритм бинарного поиска только отсталые люди применяю в случае, когда необходимо осуществить поиск на больших массивах многократно. Сейчас применяют "сбалансированное дерево", "красно-чёрное дерево", хеширование (хеш-функции).
поправил
https://onlinegdb.com/RtTtX3vah
https://onlinegdb.com/RtTtX3vah
Ибрагим Федоров
Антон, спасибочки вам, но что то все равно ошибки выдаёт(
Sungat Esenov
какие?
Похожие вопросы
- Помогите, пожалуйста, исправить ошибку в коде (C++).
- Нужен текст программы, только чтоб без ошибки запустился в Dev-c-++ Нужно как можно быстрее
- Доброго всем дня. Помогите с заданием по программированию С++ (Программа Dev-C++)
- Доброго всем дня. Помогите с заданием по программированию С++ (Программа Dev-C++)
- Выдаёт ошибку в коде.Помогите
- Программа выдает ошибку c++
- Задача на максимальное произведение в векторе C++ Где ошибка в коде?
- Си. Программа выдаёт ошибку
- Почему Visual studio выдаёт ошибку работы с памятью, если она была выделена calloc-ом?
- C++. Где ошибка?Необходимо определенное количество раз выполнить поиск номера элемента в массиве по его значению.