计算方法中的二分法

《计算方法中的二分法》有 1 条评论

1. younger 说：

   2007 年 11 月 18 日下午 9:23

   转: 

   main()

   {int i, j, number, low, hig, mid, a[11], find;

     printf(“please input 10 sorted numbers:\n”);

     for (i=1;i<=10;i++)    scanf(“%d”,&a[i]); printf(“\n”);

     printf(“please input the number to be searched:”);

     scanf(“%d”,&number);printf(“\n”);

     low=1; hig=10; find=0;

     while ((find==0)&&(low<=hig))

        {mid=(low+hig)/2;

         If  (number==a[mid])    find=mid;

         else if  (number<a[mid])   hig=mid-1;

         else  low =mid+1;}

     if  (find==0) printf(“%d is not found\n”,number);

     else printf(“%d is the %dth number .\n ”,number,find);}

    

    

    

   折半查找的基本思想：

   •首先将待查数据k与排好序（递增有序）的一组数据的中间位置上的数据进行比较，若相等，则查找成功；

   •若k>a[mid]，则待查数据k只可能出现在右半部a[mid+1…n]中,则应在这个右半部中再进行折半查找；

   •若k<a[mid]，则待查数据k只可能出现在左半部a[1…mid-1]中,则应在这个左半部中再进行折半查找；

   •这样通过逐步缩小查找范围，直到找到或找不到该数据k为止。