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

奥普瓯江

原理：


备注：


代码：

#include <stdio.h>
#include <stdlib.h>

void First_N(int str[], int G, int N);
void First_N(int str[], int G, int N)
{
    int h, z = G, x;

    if(str[G - 1] == N)     //最后一个数无法判断所以在这里直接判断如果是最后一个数相等，那么就减少程序的执行时间
    {
        printf("已在链表中找到相似数字%d在第%d位置\n", N, G);
        return;
    }
    while(G > 1)
    {
        if(G % 2 != 0)      //判断是否能被整除如果不能被整除就加1
        {
            x = 1;
        }
        else
        {
            x = 0;
        }
        G = G / 2;          //除2取到中间有多少个数据传给G变量
        G += x;
        h = z - G;          //用G 定位在数组中的位置剩余总数据量减去中间数据量
        if(str[h - 1] == N)
        {
            printf("已在链表中找到相似数字%d在第%d位置\n", N, h);
            return;
        }
        else if(str[h - 1] > N)     //数组中间节点内的数据大于N中的数据，想让N与齐匹配职能把后面的坐标向前移动也就是中间变脸h传给了z
        {
            z = h;
        }
    }
    printf("未找到数据！");
}
int main()
{
    int N;
    //int str[2] = {1, 2};
    //int str[11] = {1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89};
    int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    printf("需要查找的数字：");
    scanf("%d", &N);
    First_N(str,11 ,N);
    return 0;
}