递归、折半查找（迭代实现）

奥普瓯江

原理：


备注：


代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. void First_N(int str[], int G, int N);
   
5. void First_N(int str[], int G, int N)
   
6. {
   
7.     int h, z = G, x;
   
8. 
   
9.     if(str[G - 1] == N)     //最后一个数无法判断所以在这里直接判断如果是最后一个数相等，那么就减少程序的执行时间
   
10.     {
    
11.         printf("已在链表中找到相似数字%d在第%d位置\n", N, G);
    
12.         return;
    
13.     }
    
14.     while(G > 1)
    
15.     {
    
16.         if(G % 2 != 0)      //判断是否能被整除如果不能被整除就加1
    
17.         {
    
18.             x = 1;
    
19.         }
    
20.         else
    
21.         {
    
22.             x = 0;
    
23.         }
    
24.         G = G / 2;          //除2取到中间有多少个数据传给G变量
    
25.         G += x;
    
26.         h = z - G;          //用G 定位在数组中的位置剩余总数据量减去中间数据量
    
27.         if(str[h - 1] == N)
    
28.         {
    
29.             printf("已在链表中找到相似数字%d在第%d位置\n", N, h);
    
30.             return;
    
31.         }
    
32.         else if(str[h - 1] > N)     //数组中间节点内的数据大于N中的数据，想让N与齐匹配职能把后面的坐标向前移动也就是中间变脸h传给了z
    
33.         {
    
34.             z = h;
    
35.         }
    
36.     }
    
37.     printf("未找到数据！");
    
38. }
    
39. int main()
    
40. {
    
41.     int N;
    
42.     //int str[2] = {1, 2};
    
43.     //int str[11] = {1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89};
    
44.     int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    
45.     printf("需要查找的数字：");
    
46.     scanf("%d", &N);
    
47.     First_N(str,11 ,N);
    
48.     return 0;
    
49. }
    

复制代码