poj 2503

http://poj.org/problem?id=2503

一道二分查找题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct node
{
    char a[20];
    char b[20];
}str[100005];
int cmp(const void *x,const void *y)
{
    node *p1 = (node *)x,*p2 = (node *)y;
    return strcmp(p1->b,p2->b);
}
char c[100005][20],d[100];
int main()
{
    int i,j,p,q,high,low;
    char *ptr;
    i = j = 0;
    do
    {
        gets(d);
        if(strcmp(d,"\0") == 0) break;
        sscanf(d,"%[^ ]",str[i].a);
        sscanf(d,"%*s %s",str[i++].b);
    }while(1);
    qsort(str,i,sizeof(node),cmp);
    while(1)
    {
        gets(c[j]);
        if(strcmp(c[j++],"\0")==0) break;
        high = i;
        low = 0;
        while(low <= high)
        {
            q = (high+low)/2;
            if(!strcmp(c[j-1],str[q].b))
            {
                printf("%s\n",str[q].a);
                break;
            }
            else if(strcmp(c[j-1],str[q].b) < 0)
            high = q-1;
            else low = q+1;
        }
        if(low > high) printf("eh\n");
    }
    return 0;
}