std::bsearch

 

C++

Язык

Понятия (концепции)

Утилиты

Строки

Контейнеры

Алгоритмы

Итераторы

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

Ввод / вывод

Локализация

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

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

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

 

Алгоритмы

Функции
Немодифицирующие линейные операции
all_of any_of none_of (C++11) (C++11) (C++11) for_each count count_if mismatch equal	find find_if find_if_not (C++11) find_end find_first_of adjacent_find search search_n
Модифицирующие линейные операции
copy copy_if (C++11) copy_n (C++11) copy_backward move (C++11) move_backward (C++11) fill fill_n transform generate generate_n remove remove_if remove_copy remove_copy_if	replace replace_if replace_copy replace_copy_if swap swap_ranges iter_swap reverse reverse_copy rotate rotate_copy random_shuffle shuffle   (C++11) unique unique_copy
Разделение
is_partitioned (C++11) partition partition_copy (C++11)	stable_partition partition_point (C++11)
Сортировка (на отсортированных промежутках)
is_sorted (C++11) is_sorted_until (C++11) 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 (C++11) make_heap	push_heap pop_heap sort_heap
Минимум/максимум
max max_element min min_element minmax (C++11) minmax_element (C++11)	lexicographical_compare is_permutation (C++11) next_permutation prev_permutation
Числовые операции
iota (C++11) accumulate inner_product	adjacent_difference partial_sum
Библиотека C
qsort	bsearch

 

Определено в заголовочном файле <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 documentation for bsearch