Что такое код bsearch


Функция bsearch

Функция bsearch() выполняет двоичный поиск в отсортированном массиве, адресуемом параметром buf , и возвращает указатель на первый член, который совпадает с искомым ключом-значением, адресуемым параметром key . Количество элементов в массиве задается параметром num , а размер (в байтах) каждого элемента — параметром size .

Для сравнения каждого элемента массива с ключом-значением используется функция, адресуемая параметром compare . Функция compare должна иметь следующее определение.

Она должна возвращать значения, описанные в следующей таблице.

Сравнение Возвращаемое значение
arg1 меньше чем arg2 Меньше нуля
arg1 равен arg2 Нуль
arg1 больше чем arg2 Больше нуля

Массив должен быть отсортирован в порядке возрастания, чтобы по самому младшему адресу содержался наименьший элемент. Если массив не содержит искомого ключа-значения, возвращается нулевой указатель.

Пример

Следующая программа считывает вводимые с клавиатуры символы и определяет, входят ли они в алфавит:

bsearch

Функция bsearch() выполняет двоичный поиск на отсортированном массиве, на который ука­зывает параметр base, и возвращает указатель на первое число, соответствующее ключу, на кото­рый указывает параметр key. Число элементов в массиве задается переменной num, а размер каж­дого элемента указывается в переменной size.

Тип size_t определен в заголовочном файле stdlib.h как unsigned int.

Функция, на которую указывает параметр compare, сравнивает элемент массива с ключом. Она должна иметь следующий прототип:
int func_name(const void *arg1, const void *arg2)

Функция обязана возвращать следующие значения:
Если arg1 меньше, чем arg2, то возвращается величина, меньшая 0.
Если arg1 равен arg2, то возвращается величина 0.
Если arg1 больше, чем arg2, то возвращается число, большее 0.

Массив должен быть отсортирован по возрастанию таким образом, что наименьший адрес со­держит наименьший элемент.

Если массив не содержит ключа, то возвращается нулевой указатель.

Следующая программа читает два символа с клавиатуры и определяет , принадлежат ли они алфавиту :
#include
#include
#inciude

char * alpha = «abcdefghijklmnopqrstuvwxyz» ;
int comp ( const void *, const void * ) ;


int main ( void )
<
char ch ;
char * p ;

do <
printf ( «Enter a character: » ) ;
scanf ( «%c%*c» , & ch ) ;
ch = tolower ( ch ) ;
p = ( char * ) bsearch ( & ch , alpha , 26 , 1 , comp ) ;
if ( p ) printf ( «is in alphabet \n » ) ;
else printf ( «is not in alphabet \n » ) ;
> while ( p ) ;
return 0 ;
>

/* сравнение двух символов */
int comp ( const void * ch , const void * s )
<
return * ( char * ) ch — * ( char * ) s ;
>

Описание функций C (Си) / C++ — bsearch

Описание функций C (Си) / C++ — bsearch

#include требуется только для объявления
функции

char *bsearch(key,base,num,width,compare);
char *key; ключ поиска
char *base; указатель на поисковую базу
данных
unsigned num,width; число и размер элементов
int (*compare)(); указатель на функцию сравнения

Функция bsearch производит двоичный поиск в отсортированном
массиве из num элементов, размер каждого элемента равен width
байт. Base — указатель на начало массива, key — значение ключа
поиска.
Аргумент compare является указателем на процедуру, постав-
ляемую пользователем, которая сравнивает два элемента массива и
возвращает значение, определяющее их отношение. В течении поиска
функция bsearch может вызывать процедуру compare один или нес-
колько раз, передавая в каждом вызове указатели на два элемента
массива. Процедура должна сравнивать элементы, а затем возвращать
одно из следующих значений.

ЗНАЧЕНИЕ СМЫСЛ ЗНАЧЕНИЯ

меньше 0 element1 меньше, чем element2

0 element1 равен element2

больше 0 element1 больше, чем element2

Функция bsearch возвращает указатель на первое вхождение
ключа key в массив, на который указывает base.
Если key не найден, функция возвращает NULL.
См. также lfind, lsearch, gsort.

/* Функция bsearch производит двоичный поиск в отсортиро-
ванном массиве для элемента «key» и возвращает указатель на
структуру, в которой находится ключ key, или возвращает NULL, ес-
ли ключа нет. */

#include
#include
#include
int compare();

/* должна быть объявлена как функция */


main (argc, argv)
int argc;
char **argv;
<

char **result;
char *key = «PATH»;

/* следующий оператор находит аргумент, начинающийся с
«PATH», в предположении, что аргументы лексикографически отсорти-
рованы */

int compare (arg1, arg2)
char **arg1, **arg2;

return(strncmp(*arg1, *arg2, strlen(*arg1)));
>.

Функции библиотеки C — bsearch ()

описание

функции библиотеки Cнедействительными * bsearch (сопзЬ пустота * ключ , сопзЬ пустота * основа, size_t nitems, size_t размер, INT (* Compar) (сопзЬ пустота *, сопзЬ пустота *)) из nitemsмассива объектов для выполнения двоичногопоиска,базовая точка , чтобы быть Найтимассив,ключевой момент , чтобы найтиэлементы,размер определяет размер каждого элемента в массиве.

Содержание массива должны быть основаны на соответствующей функции сравненияCOMPAR в порядке возрастания.

заявление

Здесь () функция утверждение bsearch.

параметры

  • ключ — указатель , чтобы найти тип элемента аннулировать *.
  • база — точка для выполнения массив указателей , чтобы найти первый тип объекта аннулировать *.
  • nitems — указывает на количество базовых элементов в массиве.

  • размер — размер каждого элемента в массиве, в байтах.
  • Compar — функция используется для сравнения двух элементов.

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

Если поиск успешен, функция возвращает указатель на указатель на массив соответствующих элементов, в противном случае она возвращает пустой указатель. ,

примеров

Следующий пример демонстрирует функцию bsearch () используется.

Давайте скомпилировать и запустить эту программу, которая приведет к следующему:

Что такое код bsearch

26 просмотра

1 ответ

34 Репутация автора

есть способ реализовать, bsearch() чтобы найти несколько экземпляров ключа.

например: (obj*)bsearch(key=r,arr,elements,sizeof(obj),(int(*)(const void*, const void*)bcompare);

Код, который я написал в настоящее время, только находит первый экземпляр и не может пройти мимо первого найденного из-за того, как он работает.

Переменные:

  • p — указатель на объект класса Info
  • target — arr char
  • list — arr obj
  • foundIndex — найден найденный элемент
  • Информационно- производный класс из базового класса


Я не могу использовать другие методы, например, std::find или написать свою собственную функцию двоичного поиска и использовать bsearch()

Я пробовал циклы внутри блока else и функцию сравнения с помощью varible foundIndex, а также используя цикл while для возвращаемого значения, проходящего через obj list arr. Есть ли способ начать с определенного индекса. Я ценю любую помощь. Я не ищу код, а общий толчок в правильном направлении. Спасибо.

Caveat — текущий код компилируется и работает как ожидалось, но функциональность, которую я хочу, не может быть выяснена мной. Google и поиск в Stackoverflow не вызвали связанной проблемы.

Ответы (1)

плюса

77133 Репутация автора

Если вы должны использовать bsearch() функцию стандартной библиотеки и убедить ее найти первый элемент, соответствующий данному ключу, то все, с чем вам действительно нужно работать, — это функция сравнения. bsearch() вернет элемент, который соответствует ключу в соответствии с этой функцией, но если более чем один элемент делает, то нет гарантии, какой из них будет возвращен.

Вы можете подойти к этому с соответствующей реализацией функции сравнения, но есть значительная проблема. Функция в некоторых случаях должна будет оценить элемент, предшествующий указанному ему, но он не должен пытаться исследовать элемент, предшествующий первому массиву. bsearch() сам не передает никакой информации о границах массива к функции сравнения.

Есть как минимум два возможных решения, ни один из них не является звездным.

  1. Сохраните нижнюю границу массива в каком-либо известном месте, к которому может обращаться функция. Например, если функция сравнения является статической функцией-членом, то, возможно, вы будете использовать статическую переменную своего класса. Но это не потокобезопасно. Вы можете сделать что-то подобное с локальными переменными потока, но даже тогда это уродливо. В любом случае, вы должны обязательно установить эту переменную надлежащим образом, прежде чем звонить bsearch() .

ИЛИ ЖЕ

  1. Убедитесь, что вы никогда не bsearch() используете первый элемент. Один из способов, которым вы могли бы это сделать, — проверить, будет ли первый элемент соответствовать (но не через функцию сравнения), и использовать его напрямую, вместо того, чтобы звонить bsearch() в том случае, если это произойдет. Я бы обернул это методом, сам, и если вы не должны этого делать, требуя, чтобы такая навязывающая дисциплина использовалась вручную, также уродлива.

Выбрав одно из вышесказанного, вы можете реализовать функцию сравнения, которая смотрит на ключ предыдущего элемента в дополнение к указанному элементу. Что-то в этом направлении (что предполагает вторую альтернативу):


bsearch, bsearch_s

Определено в заголовке
(1)
(2) (поскольку C11)

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

параметры

ключ указатель на элемент для поиска
PTR указатель на массив для проверки
подсчитывать количество элементов в массиве
размер размер каждого элемента в массиве в байтах
комп функция сравнения, которая возвращает отрицательное целочисленное значение, если первый аргумент меньше второго,

положительное целочисленное значение, если первый аргумент больше второго и нулевой, если аргументы равны. key передается как первый аргумент, элемент из массива как второй.
Подпись функции сравнения должна быть эквивалентна следующему:

int cmp ( const void * a, const void * b ) ;

Функция не должна изменять объекты, переданные ей, и должна возвращать согласованные результаты при вызове для тех же объектов, независимо от их позиций в массиве.

контекст — дополнительная информация (например, последовательность сортировки), переданная в comp в качестве третьего аргумента

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

Заметки

Несмотря на название, ни стандарты C, ни POSIX не требуют, чтобы эта функция выполнялась с помощью двоичного поиска или выполняла любые гарантии сложности.

В отличие от других проверенных функций, bsearch_s не обрабатывает массивы нулевого размера как нарушение ограничения времени выполнения и вместо этого указывает, что элемент не найден (другая функция, которая принимает массивы нулевого размера, является qsort_s ).

До bsearch_s пользователи bsearch часто использовали глобальные переменные для передачи дополнительного контекста функции сравнения.

C library function — bsearch()

Description


The C library function void *bsearch(const void *key, const void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *)) function searches an array of nitems objects, the initial member of which is pointed to by base, for a member that matches the object pointed to, by key. The size of each member of the array is specified by size.

The contents of the array should be in ascending sorted order according to the comparison function referenced by compar.

Declaration

Following is the declaration for bsearch() function.

Parameters

key − This is the pointer to the object that serves as key for the search, type-casted as a void*.

base − This is the pointer to the first object of the array where the search is performed, type-casted as a void*.

nitems − This is the number of elements in the array pointed by base.

size − This is the size in bytes of each element in the array.

compare − This is the function that compares two elements.

Return Value

This function returns a pointer to an entry in the array that matches the search key. If key is not found, a NULL pointer is returned.

Example

The following example shows the usage of bsearch() function.

Let us compile and run the above program that will produce the following result −

bsearch, bsearch_s


int ( * comp ) ( const void * , const void * , void * ) ,

Language
headers
Type support
Dynamic memory management
Error handling
Program utilities
Variadic function support
Date and time utilities
Strings library
Algorithms
Numerics
Input/output support
Localization support
Thread support (C11)
Atomic operations (C11)
(2) (since C11)

If the array contains several elements that comp would indicate as equal to the element searched for, then it is unspecified which element the function will return as the result.

Parameters

key pointer to the element to search for
ptr pointer to the array to examine
count number of element in the array
size size of each element in the array in bytes
comp comparison function which returns ​a negative integer value if the first argument is less than the second,

a positive integer value if the first argument is greater than the second and zero if the arguments are equal. key is passed as the first argument, an element from the array as the second.
The signature of the comparison function should be equivalent to the following:

int cmp ( const void * a, const void * b ) ;

The function must not modify the objects passed to it and must return consistent results when called for the same objects, regardless of their positions in the array.

context — additional information (e.g., collating sequence), passed to comp as the third argument

Return value

Notes

Despite the name, neither C nor POSIX standards require this function to be implemented using binary search or make any complexity guarantees.

Unlike other bounds-checked functions, bsearch_s does not treat arrays of zero size as a runtime constraint violation and instead indicates element not found (the other function that accepts arrays of zero size is qsort_s ).

Until bsearch_s , users of bsearch often used global variables to pass additional context to the comparison function.

Что такое код bsearch

Самая актуальная документация по Visual Studio 2020: Документация по Visual Studio 2020.


Выполняет двоичный поиск по отсортированному массиву. Существует более безопасная версия этой функции, см. раздел bsearch_s.

Параметры

key
Искомый объект.

base
Указатель на начало данных, где будет производиться поиск.

num
Число элементов.

width
Ширина элементов.

compare
Функция обратного вызова, которая сравнивает два элемента. Первый — это указатель на ключ для поиска, а второй — указатель на элемент массива, который будет сравниваться с ключом.

bsearch Возвращает указатель на возникновение key в массиве, который указывает base . Если key не найден, функция возвращает NULL . Если массив не отсортирован по возрастанию или содержит повторяющиеся записи с одинаковыми ключами, результат будет непредсказуемым.

Функция bsearch выполняет двоичный поиск по отсортированному массиву, состоящему из num элементов размером width байт каждый. Значение base — это указатель на начало массива, в котором должен производиться поиск, а key — искомое значение. Параметр compare — это указатель на предоставляемую пользователем подпрограмму, которая сравнивает заданный ключ с элементом массива и возвращает одно из следующих значений, показывающих, как соотносятся значения ключа и элемента массива:

Значение, возвращаемое подпрограммой compare Описание
Ключ больше, чем элемент массива.

Эта функция проверяет свои параметры. Если compare , key или num — NULL , или если base — NULL и * num имеет ненулевое значение, или если width равен нулю, вызывается обработчик недопустимого параметра, как описано в проверки параметров. Если выполнение может быть продолжено, параметр errno устанавливается в значение EINVAL , и функция возвращает значение NULL .

Подпрограмма Обязательный заголовок
bsearch и

Дополнительные сведения о совместимости см. в разделе Совместимость во введении.

Программа сортирует массив строк с помощью qsort, а затем использует bsearch для поиска слова «cat».

Что такое код bsearch

26 просмотра


1 ответ

34 Репутация автора

есть способ реализовать, bsearch() чтобы найти несколько экземпляров ключа.

например: (obj*)bsearch(key=r,arr,elements,sizeof(obj),(int(*)(const void*, const void*)bcompare);

Код, который я написал в настоящее время, только находит первый экземпляр и не может пройти мимо первого найденного из-за того, как он работает.

Переменные:

  • p — указатель на объект класса Info
  • target — arr char
  • list — arr obj
  • foundIndex — найден найденный элемент
  • Информационно- производный класс из базового класса

Я не могу использовать другие методы, например, std::find или написать свою собственную функцию двоичного поиска и использовать bsearch()

Я пробовал циклы внутри блока else и функцию сравнения с помощью varible foundIndex, а также используя цикл while для возвращаемого значения, проходящего через obj list arr. Есть ли способ начать с определенного индекса. Я ценю любую помощь. Я не ищу код, а общий толчок в правильном направлении. Спасибо.

Caveat — текущий код компилируется и работает как ожидалось, но функциональность, которую я хочу, не может быть выяснена мной. Google и поиск в Stackoverflow не вызвали связанной проблемы.

Ответы (1)

плюса

77133 Репутация автора

Если вы должны использовать bsearch() функцию стандартной библиотеки и убедить ее найти первый элемент, соответствующий данному ключу, то все, с чем вам действительно нужно работать, — это функция сравнения. bsearch() вернет элемент, который соответствует ключу в соответствии с этой функцией, но если более чем один элемент делает, то нет гарантии, какой из них будет возвращен.

Вы можете подойти к этому с соответствующей реализацией функции сравнения, но есть значительная проблема. Функция в некоторых случаях должна будет оценить элемент, предшествующий указанному ему, но он не должен пытаться исследовать элемент, предшествующий первому массиву. bsearch() сам не передает никакой информации о границах массива к функции сравнения.

Есть как минимум два возможных решения, ни один из них не является звездным.

  1. Сохраните нижнюю границу массива в каком-либо известном месте, к которому может обращаться функция. Например, если функция сравнения является статической функцией-членом, то, возможно, вы будете использовать статическую переменную своего класса. Но это не потокобезопасно. Вы можете сделать что-то подобное с локальными переменными потока, но даже тогда это уродливо. В любом случае, вы должны обязательно установить эту переменную надлежащим образом, прежде чем звонить bsearch() .

ИЛИ ЖЕ

  1. Убедитесь, что вы никогда не bsearch() используете первый элемент. Один из способов, которым вы могли бы это сделать, — проверить, будет ли первый элемент соответствовать (но не через функцию сравнения), и использовать его напрямую, вместо того, чтобы звонить bsearch() в том случае, если это произойдет. Я бы обернул это методом, сам, и если вы не должны этого делать, требуя, чтобы такая навязывающая дисциплина использовалась вручную, также уродлива.

Выбрав одно из вышесказанного, вы можете реализовать функцию сравнения, которая смотрит на ключ предыдущего элемента в дополнение к указанному элементу. Что-то в этом направлении (что предполагает вторую альтернативу):

Илон Маск рекомендует:  Что такое код asp сброс
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL