Пространства имён
Варианты
Действия

std::bsearch

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
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

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

(шаблон функции) [править]
C documentation for bsearch