Namespaces
Variants

bsearch, bsearch_s

From cppreference.net
C
Algorithms
(C11)
bsearch bsearch_s
(C11)
헤더 파일에 정의됨 <stdlib.h>
void * bsearch ( const void * key, const void * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(1)
void * bsearch_s ( const void * key, const void * ptr, rsize_t count, rsize_t size,

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

void * context ) ;
(2) (C11부터)
/*QVoid*/ * bsearch ( const void * key, /*QVoid*/ * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(3) (C23부터)
/*QVoid*/ * bsearch_s ( const void * key, /*QVoid*/ * ptr, rsize_t count, rsize_t size,

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

void * context ) ;
(4) (C23부터)
1) ptr 이 가리키는 배열에서 key 가 가리키는 요소와 동일한 요소를 찾습니다. 배열은 count 개의 요소를 포함하며 각 요소의 크기는 size 바이트입니다. 배열은 key 를 기준으로 분할되어야 합니다. 즉, 비교 시 더 작은 모든 요소는 동일한 요소보다 앞에 나타나야 하고, 동일한 요소는 키 객체보다 큰 모든 요소보다 앞에 나타나야 합니다. 완전히 정렬된 배열은 이러한 요구 사항을 충족합니다. 요소는 comp 가 가리키는 함수를 사용하여 비교됩니다. 배열이 comp 가 사용하는 동일한 기준에 따라 오름차순으로 *key 에 대해 이미 분할되지 않은 경우 동작은 정의되지 않습니다.
2) (1) 과 동일하지만, 추가 상태 인수 context 가 comp 에 전달되며, 런타임에 다음 오류들이 검출되어 현재 설치된 constraint handler 함수를 호출한다는 점이 다릅니다:
  • count 또는 size 가 RSIZE_MAX 보다 큰 경우
  • key , ptr 또는 comp 가 null 포인터인 경우 ( count 가 0이 아닐 때)
모든 bounds-checked 함수들과 마찬가지로, bsearch_s (및 해당 타입-제네릭 매크로) (C23부터) 는 구현체가 __STDC_LIB_EXT1__ 를 정의하고, 사용자가 <stdlib.h> 를 포함하기 전에 __STDC_WANT_LIB_EXT1__ 를 정수 상수 1 로 정의한 경우에만 사용 가능함이 보장됩니다.
3,4) (1) 번 및 (2) 번에 각각 대응하는 타입-제네릭 매크로입니다. T 를 한정자가 없는 객체 타입( void 포함)으로 가정합니다.
  • ptr 이 const T * 타입인 경우, 반환 타입은 const void * 입니다.
  • 그렇지 않고 ptr 이 T * 타입인 경우, 반환 타입은 void * 입니다.
  • 그 외의 경우 동작은 정의되지 않습니다.
이러한 제네릭 함수들의 매크로 정의가 실제 함수에 접근하기 위해 억제된 경우(예: ( bsearch ) , ( bsearch_s ) 또는 함수 포인터 사용), 실제 함수 선언인 (1) 번 또는 (2) 번이 표시됩니다.

배열에 검색된 요소와 동일하다고 comp 가 판단하는 여러 요소가 포함된 경우, 함수가 결과로 어떤 요소를 반환할지는 명시되어 있지 않습니다.

실제 함수의 직접 사용 (1) 과 (2) 는 사용이 권장되지 않습니다.

(since C23)

목차

매개변수

key - 검색할 요소에 대한 포인터
ptr - 검사할 배열에 대한 포인터
count - 배열의 요소 개수
size - 배열 내 각 요소의 크기(바이트 단위)
comp - 비교 함수. 첫 번째 인수가 두 번째 인수보다 작으면 음의 정수 값을, 첫 번째 인수가 두 번째 인수보다 크면 양의 정수 값을, 인수들이 동등하면 0을 반환합니다. key 가 첫 번째 인수로, 배열의 요소가 두 번째 인수로 전달됩니다.

비교 함수의 시그니처는 다음에 상응해야 합니다:

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

이 함수는 전달된 객체를 수정해서는 안 되며, 배열 내 위치에 관계없이 동일한 객체에 대해 호출될 때 일관된 결과를 반환해야 합니다.

​

context - 비교자의 상태(예: 정렬 순서), comp 에 세 번째 인수로 전달됨

반환값

1) 배열 내에서 * key 와 동일하게 비교되는 요소에 대한 포인터, 또는 해당 요소를 찾지 못한 경우 널 포인터.
2) (1) 과 동일하지만, 런타임 제약 조건 위반 시 널 포인터도 반환됩니다.
3,4) (1) 및 (2) 과 각각 동일하나, cv 한정자가 조정됩니다.

참고 사항

이름과는 달리, C나 POSIX 표준은 이 함수가 이진 탐색을 사용하여 구현되어야 한다거나 복잡도에 대한 어떤 보장도 요구하지 않습니다.

다른 경계 검사 함수들과 달리, bsearch_s 는 크기가 0인 배열을 런타임 제약 조건 위반으로 처리하지 않고 요소를 찾지 못했음을 표시합니다(크기가 0인 배열을 허용하는 다른 함수는 qsort_s 입니다).

bsearch_s 가 도입되기 전까지, bsearch 사용자들은 비교 함수의 상태를 나타내기 위해 전역 변수를 자주 사용했습니다.

예제

이 코드 실행 
#include <stdlib.h>
#include <stdio.h>
struct data {
    int nr;
    char const *value;
} dat[] = {
    {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"}
};
int data_cmp(void const *lhs, void const *rhs) 
{
    struct data const *const l = lhs;
    struct data const *const r = rhs;
    if (l->nr < r->nr) return -1;
    else if (l->nr > r->nr) return 1;
    else return 0;
    // return (l->nr > r->nr) - (l->nr < r->nr); // possible shortcut
    // return l->nr - r->nr; // erroneous shortcut (fails if INT_MIN is present)
}
int main(void) 
{
    struct data key = { .nr = 3 };
    struct data const *res = bsearch(&key, dat, sizeof dat / sizeof dat[0],
                                     sizeof dat[0], data_cmp);
    if (res) {
        printf("No %d: %s\n", res->nr, res->value);
    } else {
        printf("No %d not found\n", key.nr);
    }
}

출력: 

No 3: Hello

참고문헌

  • C17 표준 (ISO/IEC 9899:2018):
  • 7.22.5.1 bsearch 함수 (p: 258)
  • K.3.6.3.1 bsearch_s 함수 (p: 441-442)
  • C11 표준 (ISO/IEC 9899:2011):
  • 7.22.5.1 bsearch 함수 (p: 355)
  • K.3.6.3.1 bsearch_s 함수 (p: 608-609)
  • C99 표준 (ISO/IEC 9899:1999):
  • 7.20.5.1 bsearch 함수 (p: 318-319)
  • C89/C90 표준 (ISO/IEC 9899:1990):
  • 4.10.5.1 The bsearch 함수

참고 항목

(C11)
지정되지 않은 타입의 요소 범위를 정렬합니다
(함수)
C++ documentation for bsearch