YB4.13 Алгоритмы поиска

RobertDeMilo

Nov 11th, 2023

106

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 3.83 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
template<typename It>
void PrintRange(It range_begin, It range_end)
{
for (auto it = range_begin; it != range_end; ++it)
{
cout << *it << " ";
}
}
int main()
{
// Перебор всех пробелов строки
// Выведем позиции всех пробелов строки s
// next(it) - более универсальный способ записать it + 1
string s;
for (auto it = find(begin(s), end(s), ' '); it != end(s); it = find(next(it), end(s), ' '))
{
cout << it - begin(s) << " ";
}
return 0;
}
// Где будем искать:
// 1 Не отсортированный вектор (или строка)
// 2 Отсортированный вектор
// 3 Множество (или словарь)
// Что будем искать и проверять:
// 1 Проверить существование конкретного элемента
// 2 Проверить существование и найти первый
// 3 Найти первый элемент, больший или равный данному
// 4 Найти первый элемент, больший данного
// 5 Подсчитать кол-во элементов
// 6 Перебрать все элементы, которые удовлетворяют данному условию или равны данному элементу
// Поиск в НЕотсортированном векторе
// find(begin(v), end(v), x);
// (Найти элемент по какому-то условию в векторе, например, первый элемент меньший либо равный данному)
// find_if(begin(v), end(v), [](int y){...});
// count(begin(v), end(v), x);
// Перебрать все можно с помощью цикла и find
// Поиск в отсортированном векторе
// binary_search (begin(v), end(v), x); Проверка на существование
// lower_bound(begin(v), end(v), x); Первый элемент, больший или равный данному
// upper_bound(begin(v), end(v), x); Первый элемент, больший данного
// equal_range(begin(v), end(v), x) == make_pair( lower_bound(...), upper_bound(...))
// Диапазон элементов, равных данному
// equal_range
// Если элемент есть,
// equal_range = [lower_bound,upper_bound) - диапазон всех вхождений
//
// Если элемента нет,
// lower_bound == upper_bound - позиция, куда можно вставить элемент без нарушения порядка сортировки
// (они будут равны)(и не всегда будут равны end) будут указывать на первый элемент больший данного
// Как найти кол-во вхождений
// upper_bound - lower_bound
//
// Как перебрать все вхождения
// Проитерировать ОТ lower_bound ДО upper_bound
// Если каждый раз уменьшаем размер вдвое, то мы проделываем ровно столько операций какова степень 2ки массива
// В какую степень нужно возвести 2 чтобы получить размер нашего диапазона
// Двоичный логарифм log2(N)
// Столько же работает поиск во множестве и словаре
// Поиск во множестве
// s.count(x);
// s.find(x);
// s.lower_bound(x);
// s.upper_bound(x);
// s.equal_range(x);

Add Comment

Please, Sign In to add comment