Free2000fly's Official Blog

typedef struct str {
char s1[11];
char s2[11];
} str, *stri;

str strContainer[100001] = { 0 };

int __cdecl qsort_cmp(const void *a, const void *b){
return strcmp( ((str *)a)->s2 , ((str *)b)->s2 );
}

//
// Callback function that compares two elements.
// The first is a pointer to the key for the search
// and the second is a pointer to the array element to be compared with the key.
//
// int __cdecl compareMyType (const void * a, const void * b)
// {
// if ( *(MyType1*)a >  *(MyType2*)b ) return 1;
// if ( *(MyType1*)a == *(MyType2*)b ) return 0;
// if ( *(MyType1*)a <  *(MyType2*)b ) return -1;
// }
//
int __cdecl compare(const void * pKey, const void * pIter) {
char * pA1 = (char*)pKey;
str * pB1 = (str*)pIter;
return strcmp(pA1, pB1->s2);
}

int main()
{
int n=0;
char szKey[250] = { 0 };

while(1) {
gets(szKey);
if(strlen(szKey)==0) break;
int i=0,j=0;
for(i=0; szKey[i]!=‘ ‘; i++) { strContainer[n].s1[i]=szKey[i]; }
strContainer[n].s1[i]=‘\0‘;
for(i++; szKey[i]!=‘\0‘; i++,j++) { strContainer[n].s2[j]=szKey[i]; }
strContainer[n].s2[j]=‘\0‘;
n++;
}

qsort(strContainer, n, sizeof(str), qsort_cmp);

while(scanf(“%s“, szKey) != EOF)
{
str * pItem = NULL;
pItem = (str *) bsearch(szKey, strContainer, n, sizeof(str), compare);
if(pItem != NULL) {
puts(pItem->s1);
} else {
printf(“eh\n“);
}
}
return 0;
}

using namespace std;

//—————————————————————————
/**************************************
template<class ForwardIterator, class Type>
bool binary_search  (
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val
);

template<class ForwardIterator, class Type, class BinaryPredicate>
bool binary_search  (
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val,
BinaryPredicate _Comp
);
//  这里需要在注意的是算法搜索时数据集必须是已经排好序的
// 排序算法可以使用 sort()
// 该算法只能搜索该数据集里面某数据存在与否
**************************************/

bool bigger(int first,int second) {
return first < second;
}

int main(int argc, char* argv[])
{
vector<int> IntVector;
vector<int>::iterator iter;
bool found1,found2;
IntVector.push_back(10);
IntVector.push_back(120);
IntVector.push_back(130);
IntVector.push_back(110);
IntVector.push_back(69);

sort(IntVector.begin(),IntVector.end());

// 注意 binary_search 算法必须经过排序数据集
// 如果在一个排好序的数据集里面
// 我们应该尽量选择binary_search算法
// 因为该算法的效率比较高

found1 = binary_search(IntVector.begin(),IntVector.end(),130);
if(found1){
cout << “search such variable“ << endl;
} else {
cout << “No such variable“ << endl;
}

found2 = binary_search(IntVector.begin(), IntVector.end(), 70, bigger);
if(found2){
cout << “search such variable“ << endl;
} else {
cout << “No such variable“ << endl;
}

found2 = binary_search(IntVector.begin(), IntVector.end(), 69, bigger);
if(found2){
cout << “search such variable“ << endl;
} else {
cout << “No such variable“ << endl;
}

return 0;
}
//—————————————————————————