std::bsearch

 

C++

Язык

Заголовочные файлы

Концепты

Поддержка языка

Ошибка

Утилиты

Строки

Контейнеры

Алгоритмы

Итераторы

Работа с числами

Ввод/вывод

Локализация

Регулярные выражения (C++11)

Атомарные операции (C++11)

Потоки (C++11)

Файловая система (C++17)

Технические спецификации

 

Алгоритмы

Функции
Немодифицирующие линейные операции
all_ofany_ofnone_of Шаблон:lines for_each countcount_if mismatch equal	findfind_iffind_if_not Шаблон:lines find_end find_first_of adjacent_find search search_n
Модифицирующие линейные операции
copycopy_if Шаблон:lines copy_n Шаблон:lines copy_backward move Шаблон:lines move_backward Шаблон:lines fill fill_n transform generate generate_n removeremove_if remove_copyremove_copy_if	replacereplace_if replace_copyreplace_copy_if swap swap_ranges iter_swap reverse reverse_copy rotate rotate_copy random_shuffleshuffle Шаблон:lines unique unique_copy
Разделение
is_partitioned Шаблон:lines partition partition_copy Шаблон:lines	stable_partition partition_point Шаблон:lines
Сортировка (на отсортированных промежутках)
is_sorted Шаблон:lines is_sorted_until Шаблон:lines sort	partial_sort partial_sort_copy stable_sort nth_element
Бинарный поиск (на отсортированных промежутках)
lower_bound upper_bound	binary_search equal_range
Множества (на отсортированных промежутках)
merge inplace_merge includes	set_difference set_intersection set_symmetric_difference set_union
Куча
is_heap is_heap_until Шаблон:lines make_heap	push_heap pop_heap sort_heap
Минимум/максимум
max max_element min min_element minmax Шаблон:lines minmax_element Шаблон:lines	lexicographical_compare is_permutation Шаблон:lines next_permutation prev_permutation
Числовые операции
iota Шаблон:lines accumulate inner_product	adjacent_difference partial_sum
Библиотека C
qsort	bsearch

 

Defined in header <cstdlib>
extern "C" void* bsearch( const void* key, const void* ptr, std::size_t count,                std::size_t size, int (*comp)(const void*, const void*) );
extern "C++" void* bsearch( const void* key, const void* ptr, std::size_t count,                std::size_t size, int (*comp)(const void*, const void*) );

Находит элемент, равный элементу, заданному по указателю key, в массиве, на который указывает ptr. Этот массив должен содержать count элементов, размером в size байт каждый, и должен быть поделён элементом, доступным по указателю key так, чтобы все элементы, которые меньше чем равные ему, находились раньше в массиве, а те, которые больше их, после них. Полностью отсортированный массив удовлетворяет этим требованиям. Элементы сравниваются, используя функцию, предоставленную по указателю comp.

Поведение не определено, если массив не был поделён относительно элемента для поиска в порядке возрастания, по тому же правилу, которое использует comp.

Если массив содержит несколько одинаковых элементов, определённых функцией comp, и равных элементу для поиска, то будет возвращён любой из таких элементов.

Параметры

key	—	Указатель на элемент для поиска
ptr	—	Указатель на массив, в котором будет искаться элемент
count	—	Количество элементов в массиве
size	—	Размер в байтах каждого элемента в массиве
comp	—	Функция, которая будет сравнивать объекты. Она возвращает отрицательное целое число, если первый аргумент этой функции меньше второго, положительное число, если первый аргумент больше второго, и наконец если они равны, то она возвращает 0. Определение сравнивающей функции должно быть следующим: int cmp(const void *a, const void *b); Эта функция не должна модифицировать переданные ей объекты. key передаётся первым аргументом, а элемент из массиве вторым.

Возвращаемое значение

Возвращается указатель на найденный элемент или нулевой указатель, если элемент не был найден.

Примечание

Несмотря на имя, стандарт С++, Си или POSIX не требует, чтобы эта функция реализовывала алгоритм "бинарного поиска" или давала каких-то гарантий по стабильности и степени сложности алгоритма.

Две перегрузки, предоставленные стандартной библиотекой C++ различны, так как типы параметра comp различны (языковое связывание является частью типа)

Пример

Запустить этот код

#include <cstdlib>
#include <iostream>
 
int compare(const void *ap, const void *bp)
{
    const int *a = (int *) ap;
    const int *b = (int *) bp;
    if(*a < *b)
        return -1;
    else if(*a > *b)
        return 1;
    else
        return 0;
}
 
int main(int argc, char **argv)
{
    const int ARR_SIZE = 8;
    int arr[ARR_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
    int key1 = 4;
    int *p1 = (int *) std::bsearch(&key1, arr, ARR_SIZE, sizeof(arr[0]), compare);
    if(p1)
        std::cout << "значение " << key1 << " найдено в позиции " << (p1 - arr) << '\n';
     else
        std::cout << "значение " << key1 << " не найдено\n";
 
    int key2 = 9;
    int *p2 = (int *) std::bsearch(&key2, arr, ARR_SIZE, sizeof(arr[0]), compare);
    if(p2)
        std::cout << "значение " << key2 << " найдено в позиции " << (p2 - arr) << '\n';
     else
        std::cout << "значение " << key2 << " не найдено\n";
}

Вывод:

значение 4 найдено в позиции 3
значение 9 не найдено

See also

qsort	Сортирует диапазон элементов любого типа (функция)
equal_range	возвращает набор элементов для конкретного ключа Оригинал: returns range of elements matching a specific key Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. (шаблон функции)
Справка по C — bsearch