Что такое быстрый метод поиска несортированного вектора? Нужно ли искать только вектор от начала до конца или использовать std :: sort, а затем использовать алгоритм бинарного поиска?Поиск несортированного вектора (C++)
Если вам нужно проверить, отсортирован ли вектор, самым быстрым методом будет использование std :: is_sorted(). Это линейное время.
Если вам нужно его отсортировать, вы можете использовать std :: sort(), который является наиболее эффективным. O (n * log n)
Итак, проверка выполняется быстрее, чем сортировка.
Теоретически, для сортировки требуется O (n log n) и нужен двоичный поиск O (log n). Для последовательного поиска требуется только O (n). Поэтому, если вам нужно только один раз выполнить поиск, последовательный поиск будет прекрасен. Если вам требуется большое количество поисков по одному и тому же вектору, амортизированная стоимость может принести пользу. –