数据结构与算法1——二分法

二分法逻辑：

• 给定N个从小到大排好序的整数序列List[]，以及某待查找整数X，
• 我们的目标是找到X在List中的下标。即若有List[i]=X，则返回i；否则返回-1表示没有找到。
•   二分法是先找到序列的中点List[M]，与X进行比较，若相等则返回中点下标；
• 否则，若List[M]>X，则在左边的子系列中查找X；若List[M]<X，则在右边的子系列中查找X。

• 最坏情况下的复杂度 log₂(n)

 

---

代码示例：

•       

   1 #include <stdio.h>
  2 #include <math.h>
  3 #define num 3
  4 void putin(double *);
  5 int search(double *);
  6 void main()
  7 {
  8     double a[num];
  9     putin(a);
  10     printf("查找到的数字的下标是%d\n",search(a));
  11 
  12 }
  13 
  14 void putin(double *a)
  15 {
  16     int i;
  17     printf("输入%d个数字",num);
  18     for(i=0;i<num;i++)
  19         scanf("%lf",(a+i));
  20 }
  21 
  22 
  23 int search(double *a)
  24 { 
  25     int m=0,n=num-1,middle;
  26     double find;
  27     printf("输入要查找的数字");
  28     scanf("%lf",&find);
  29     while(m<=n)
  30     {middle=(m+n)/2;
  31       if(find==a[middle]) return middle;
  32      else if(find<a[middle]) n=middle-1;
  33      else if(find>a[middle]) m=middle+1;
  34     }
  35     return -1;
  36      
  37   
  38 }