Technical Reference: Base Operating System and Extensions, Volume 1

bsearch Subroutine

Purpose

Performs a binary search.

Library

Standard C Library (libc.a)

Syntax

#include <stdlib.h>

void *bsearch ( Key, Base, NumberOfElements, Size, ComparisonPointer)

const void *Key; 
const void *Base;
size_t NumberOfElements;
size_t Size;
int (*ComparisonPointer) (const void *, const void *);

Description

The bsearch subroutine is a binary search routine.

The bsearch subroutine searches an array of NumberOfElements objects, the initial member of which is pointed to by the Base parameter, for a member that matches the object pointed to by the Key parameter. The size of each member in the array is specified by the Size parameter.

The array must already be sorted in increasing order according to the provided comparison function ComparisonPointer parameter.

Parameters

Key	Points to the object to be sought in the array.
Base	Points to the element at the base of the table.
NumberOfElements	Specifies the number of elements in the array.
ComparisonPointer	Points to the comparison function, which is called with two arguments that point to the Key parameter object and to an array member, in that order.
Size	Specifies the size of each member in the array.

Return Values

If the Key parameter value is found in the table, the bsearch subroutine returns a pointer to the element found.

If the Key parameter value is not found in the table, the bsearch subroutine returns the null value. If two members compare as equal, the matching member is unspecified.

For the ComparisonPointer parameter, the comparison function compares its parameters and returns a value as follows:

If the first parameter is less than the second parameter, the ComparisonPointer parameter returns a value less than 0.
If the first parameter is equal to the second parameter, the ComparisonPointer parameter returns a value of 0.
If the first parameter is greater than the second parameter, the ComparisonPointer parameter returns a value greater than 0.

The comparison function need not compare every byte, so arbitrary data can be contained in the elements in addition to the values being compared.

The Key and Base parameters should be of type pointer-to-element and cast to type pointer-to-character. Although declared as type pointer-to-character, the value returned should be cast into type pointer-to-element.

Related Information

The hsearch (hsearch, hcreate, or hdestroy Subroutine) subroutine, lsearch (lsearch or lfind Subroutine) subroutine, qsort subroutine.

Knuth, Donald E.; The Art of Computer Programming, Volume 3. Reading, Massachusetts, Addison-Wesley, 1981.

Searching and Sorting Example Program and Subroutines Overview in AIX 5L Version 5.2 General Programming Concepts: Writing and Debugging Programs.