之前提交的简单排序，顺序查找，后来改成归并排序加二分查找，最后翻书发现快速排序跟快，改后加上二分查找终于通过了！！！
以前上课老师讲的都还给他了！每次做题都习惯用简单排序，看来要做多看书！
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char chip[100001][30];
char bhip[100001][30];
int  idex[100001];
char w[50];
int L,yes;
void qs(int low,int heigh)
{
	int qid,i,j;
	if(low<heigh)
	{
		qid=idex[low];
		i=low;
		j=heigh;
		while(i<j)
		{
			while(i<j&&strcmp(bhip[idex[j]],bhip[qid])>=0) 
				j--;
			if(i<j)
				idex[i++]=idex[j];
			while(i<j&&strcmp(bhip[idex[i]],bhip[qid])<=0)
				i++;
			if(i<j)
				idex[j--]=idex[i];
		}
		idex[i]=qid;
		qs(low,j-1);
		qs(i+1,heigh);
	}
}
void main()
{
	int i,j,k,t;
	L=0;
	while(gets(w)!=NULL&&w[0]!='\0')
	{
		sscanf(w,"%s %s",chip[L],bhip[L]);
		idex[L]=L;
		L++;
	}
	qs(0,L-1);
	while(gets(w)!=NULL)
	{
		i=0;
		j=L-1;
		yes=0;
		while(i<=j)
		{
			k=(i+j)/2;
			t=strcmp(bhip[idex[k]],w);
			if(t>0)
			{
				j=k-1;
			}
			else if(t<0)
			{
				i=k+1;
			}
			else
			{
				yes=1;
				break;
			}

		}
		if(yes==1)
			printf("%s\n",chip[idex[k]]);
		else
		{
			printf("eh\n");
		}

	}
}

• Re:快速排序，加二分查找！！ (1286) huangchang9001 2011-03-17 16:10:09
• Re:快速排序，加二分查找！！ (59) szxyj 2011-03-26 15:59:27
  • Re:快速排序，加二分查找！！ (35) huangchang9001 2011-03-26 21:37:11
  • Re:快速排序，加二分查找！！ (35) huangchang9001 2011-03-26 21:37:14
• Re:快速排序，加二分查找！！ (1286) Yikkkke 2020-06-08 20:34:45