1£©¶þ·Ö·¨²éÕҵĸÅÄî
¶þ·Ö²éÕÒÓÖ³ÆÕÛ°ë²éÕÒ£¬ËüÊÇÒ»ÖÖЧÂʽϸߵIJéÕÒ·½·¨¡£
¶þ·Ö²éÕÒÒªÇó£ºÏßÐÔ±íÊÇÓÐÐò±í£¬¼´±íÖнáµã°´¹Ø¼ü×ÖÓÐÐò£¬²¢ÇÒÒªÓÃÏòÁ¿×÷Ϊ±íµÄ´æ´¢½á¹¹¡£²»·ÁÉèÓÐÐò±íÊǵÝÔöÓÐÐòµÄ¡£
2£©¶þ·Ö·¨²éÕÒµÄÌصã
¶þ·Ö²éÕÒµÄÌصã¾ÍÊÇ´Ó±íÖм俪ʼ²éÕÒÄ¿±êÔªËØ¡£Èç¹ûÕÒµ½Ò»ÖÂÔªËØ£¬Ôò²éÕҳɹ¦¡£Èç¹ûÖмäÔªËرÈÄ¿±êÔªËØС£¬ÔòÈÔÓöþ·Ö²éÕÒ·½·¨²éÕÒ±íµÄºó°ë²¿·Ö(±íÊǵÝÔöÅÅÁеÄ)£¬·´Ö®ÖмäÔªËرÈÄ¿±êÔªËØ´ó£¬Ôò²éÕÒ±íµÄÇ°°ë²¿·Ö¡£
µ±Êý¾ÝÁ¿ºÜ´óÊÊÒ˲ÉÓø÷½·¨¡£²ÉÓöþ·Ö·¨²éÕÒʱ£¬Êý¾ÝÐèÊÇÅźÃÐòµÄ¡£
3£©¶þ·Ö·¨²éÕҵĻù±¾Ë¼Ïë
£¨Éè²éÕÒµÄÊý×éÇø¼äΪarray[low, high]£©
£¨1£©È·¶¨¸ÃÇø¼äµÄÖмäλÖÃK
£¨2£©½«²éÕÒµÄÖµTÓëarray[k]±È½Ï¡£ÈôÏàµÈ£¬²éÕҳɹ¦·µ»Ø´ËλÖã»·ñÔòÈ·¶¨ÐµIJéÕÒÇøÓò£¬¼ÌÐø¶þ·Ö²éÕÒ¡£ÇøÓòÈ·¶¨ÈçÏ£º
array[k]>T ÓÉÊý×éµÄÓÐÐòÐÔ¿ÉÖªarray[k,k+1,¡¡,high]>T;¹ÊеÄÇø¼äΪarray[low,¡¡£¬K-1]b.array[k]<T ÀàËÆÉÏÃæ²éÕÒÇø¼äΪarray[k+1,¡¡£¬high]¡£Ã¿Ò»´Î²éÕÒÓëÖмäÖµ±È½Ï£¬¿ÉÒÔÈ·¶¨ÊÇ·ñ²éÕҳɹ¦£¬²»³É¹¦µ±Ç°²éÕÒÇø¼äËõСһ°ë£¬µÝ¹éÕÒ£¬¼´¿É¡£
4£©ÔÚÓÐÐòµÄÓÐN¸öÔªËصÄÊý×éÖвéÕÒÓû§Êä½øÈ¥µÄÊý¾Ýx¡£
Ëã·¨ÈçÏ£º
a£©È·¶¨²éÕÒ·¶Î§front=0£¬end=N-1£¬¼ÆËãÖÐÏîmid=£¨front+end£©/2¡£
b£©Èôa[mid]=x»òfront>=end,Ôò½áÊø²éÕÒ£»·ñÔò£¬ÏòϼÌÐø¡£
3£©Èôa[mid]<x,˵Ã÷´ý²éÕÒµÄÔªËØÖµÖ»¿ÉÄÜÔÚ±ÈÖÐÏîÔªËØ´óµÄ·¶Î§ÄÚ£¬Ôò°Ñmid+1µÄÖµ¸³¸øfront£¬²¢ÖØмÆËãmid£¬×ªÈ¥Ö´Ðв½Öèb£»
Èôa[mid]>x£¬ËµÃ÷´ý²éÕÒµÄÔªËØÖµÖ»¿ÉÄÜÔÚ±ÈÖÐÏîÔªËØСµÄ·¶Î§ÄÚ£¬Ôò°Ñmid-1µÄÖµ¸³¸øend£¬²¢ÖØмÆËãmid£¬×ªÈ¥Ö´Ðв½Öèb¡£
³ÌÐòʾÀýÈçÏ£º
#include<stdio.h>
void binary(int *s,int num,int n); int rebinary(int *s,int num,int left,int right);
int main() { int b[]={1,3,6,8,5,4,22,33,9,10,11,45,67,78,99}; int num,temp; int n; int i,j;
n=sizeof(b)/sizeof(b[0]); /*Èç¹ûÁÐ±í²»ÊÇÓÐÐòµÄÊý¾ÝµÄ¼¯ºÏ£¬ÔòÐèÒªÔÚ¶þ·Ö·¨²éÕÒ֮ǰ£¬ÏȶÔÊý£¬½øÐÐÅÅÐò*/ for(i=0;i<n;i++) for(j=0;j<n-1-i;j++) if(b[j]>b[j+1])//´ÓСµ½´óÅÅÐò { temp=b[j]; b[j]=b[j+1]; b[j+1]=temp; } printf("¸Ã×éÊýÅÅÐòÖ®ºóµÄÐòÁбíΪ£º"); for(i=0;i<n;i++) printf("%d ",b[i]); printf("\n");
printf("ÇëÊäÈëÒª²éÕÒµÄÊý£º"); scanf("%d",&num);
binary(b,num,n);
rebinary(b,num,0,n);
} //·ÇµÝ¹é¶þ·Ö·¨²éÕÒ void binary(int *s,int num,int n) { int mid; int left=0; int right=n-1;
mid=(left+right)/2;
while(left<right && s[mid]!=num) { if(s[mid]<num) //ÖмäµÄÊýСÓÚÒª²éÕÒµÄÊý£¬¾Í´ÓÖмäÆ«ÓÒ²éÕÒ left=mid+1; else if(s[mid]>num)//ÖмäµÄÊý´óÓÚÒª²éÕÒµÄÊý£¬¾Í´ÓÖмäÆ«×ó²éÕÒ right=mid-1; mid=(right+left)/2; } if(s[mid]==num) { printf("ÒÑÕÒµ½ %d ,Ëù´¦µÄϱêΪ%d\n",num,mid); } else printf("sorry£¬Ã»ÓÐÕÒµ½%d\n",num); return ; }
//µÝ¹é¶þ·Ö·¨
int rebinary(int *s,int num,int left,int right) { int mid;
if(left>right) { printf("¶Ô²»Æð£¬Ã»ÓÐÕÒµ½%d\n",num); return -1; } mid=(left+right)/2;
if(s[mid]==num) { printf("ÒÑÕÒµ½ %d ,Ëù´¦µÄϱêΪ%d\n",num,mid); } else if(s[mid]<num) return rebinary(s,num,mid+1,right); else return rebinary(s,num,left,mid-1);
} |