二分查找法c程序.txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

分治法之快速排序法与二分法查找C语言源代码[原创] 
        所谓分治法，意思是“分而治之”，即把大的问题分成多个小规模的问题，逐一解决，而拆分以后的“小问题”往往可以用同样的操作去解决。

        利用分治法，可以对数据快速排序。即找一个“支点”，把大于该数据的数据放到后面，把小于该数据的数据放到前面；然后对该“支点”两边的数据做同样处理。

        利用分治法，可以在已排序的数据中快速查找指定数据。先看中间数据（支点）是否为要找的数据，若是，则返回；否则，则要找的数据要么在支点的前半部分，要么在该支点的后半部分。重复进行即可。

＃i nclude <stdlib.h>
＃i nclude <conio.h>

int partition(int array[],int p,int r)
{/*寻找支点*/
   int i=p,j=r+1;
   int x=array[p];
   int t;
   while(1)
   {
      while(array[++i]<x);
      while(array[--j]>x);
      if(i>=j)
           break;
      t=array[i];
      array[i]=array[j];
      array[j]=t;
   }
   array[p]=array[j];
   array[j]=x;
   return j;
}
void fast(int array[],int start,int end)
{
   if(start<end)
   {
      int i=partition(array,start,end);
      fast(array,start,i-1);/*对支点的前半部分排序*/
      fast(array,i+1,end);/*对支点的后半部分排序*/
   }
}

void output(int array[],int n)
{/*输出数据*/
   int i;
   for(i=0;i<n;i++)
   {
      if(i%10==0)/*每行输出10个数据*/
           printf("\n");
      printf("%4d",array[i]);
   }
}

int binary(int array[],int n,int value)
{/*二分法查找,数据已按从小到大排序*/
  int i=0,j=n-1,k=n/2;
  while(i<=j)
  {
     k=(i+j)/2;
     if(array[k]==value)/*找到,返回*/
          return k;
     else if(array[k]>value)/*前半部分*/
          j=k-1;
     else if(array[k]<value)/*后半部分*/
          i=k+1;
  }
  return -1;/*没有找到*/
}

void main()
{
   int array[100],i,value,k;
   clrscr();
   for(i=0;i<100;i++)/*随机产生数据,最好在前面使用随机种子*/
      array[i]=random(500);
   printf("\nBefore sorting.....\n");
   output(array,100);
   fast(array,0,99);
   printf("\nAfter sorting......\n");
   output(array,100);
   printf("\nInput the number to search.\n");
   scanf("%d",&value);
   if((k=binary(array,100,value))!=-1)
      printf("\nOK.I find it.It is:%d.and its position is:%d\n",array[k],k);
   else
      printf("\nSorry.\n");
}