Saturday, January 23, 2010

C/C++ Binary Search function in Standard Library

C/C++ хэлний стандарт сангуудын нэлээд хүчирхэг нэгэн Функц болох bsearch функц stdlib.h/cstdlib толгой файлд тодорхойлогдсон байдаг. Хэрэв өгөгдсөн элемэнт өгөгдсөн эрэмбэлэгдсан массивт байхгүй бол NULL заагчийг буцаадаг.
void * bsearch ( const void * key, const void * base, size_t num, 
size_t size, int ( * comparator ) ( const void *, const void * ) );
key - хайж буй элемэнтийн санах ойд эзлэх хаяг
base - хайлт хийж буй массив
num - массивт хайлт хийх хэмжээ
size - массивийн өгөгдлийн төрлийн санах ойд эзлэх хэмжээ
compareFunction - харьцуулалт хийх функийн нэр. Харьцуулалт хийх функцийг миний өмнө бичсэн qsort() функцийг ашиглахад хэрэглэх зарчимтай ижил.
int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a <  *(MyType*)b ) return -1;
}

Жишээ код:

#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a,const void *b) {
        int *x = (int *) a;
        int *y = (int *) b;
        return *x - *y;
}
int baseArray[] = {78, 648, 64, 387, 2, 93, 19, 57};
int main(){
    int *result;
    int key = 57;
    qsort(baseArray, 8, sizeof(int), compare_int);
    result = (int*) bsearch(&key, baseArray, 8, sizeof(int), compare_int);
    if(result != NULL){
        printf("%d element baseArray massivt aguulagdaj bn.\n", key);          
    }else{
        printf("%d element baseArray massivt aguulagdaagui bn.\n", key);      
    }
return 0;
}

No comments: