二分查找法（递归与非递归方式）

思想：
首先要确保数组中数是按顺序排列好的，假设我们要查找的数为277。要查找的数277：

• 比较277与中间数的大小，如果刚好为277，则就算找到。如果大于277，排除另外一半，然后把新的half_num-1设置为上界。同理，如果小于277，则把half_num+1设置为下界 。然后继续重复之前的步骤。

一、非递归

#include <stdio.h>
void create_num(int arr[])
{
    int i=0,n=1;
    for (;i<1024;i++)
    {
        n++;
        arr[i]=n;
    }
}

void find_num(int arr[])   //遍历数组查找法
{
    int i=0;
    for(;i<1024;i++)
    {
        if(arr[i] == 277)
        {
            printf("use the %d times to find it\n",i+1);
        }
    }
}

void half_find(int arr[]) //二分查找法
{
    int first_num = 0;
    int last_num = 1023;
    int half_num = 0;
    int flags=0;  

    while (first_num < last_num)
    {
        half_num = (first_num + last_num)/2;
        if( arr[half_num] == 277)   // 277是我要找到数
        {
            flags++;
            printf("use %d times to find it\n",flags);
            break;
        }
        else if( arr[half_num] > 277)
        {
            flags++;
            last_num=half_num-1;   //中间数减一作为上边界
        }
        else
        {
            flags++;
            first_num=half_num+1; //中间数加一作为下边界
        }
    }
}
void main()
{
    int arr[1024]={0};
    create_num(arr);
    find_num(arr);
    half_find(arr);
}

---

二、递归方式：

因为二分法查找就是不断重复同一个动作。所以可以用递归来实现，和一般方式类似。

#include <stdio.h>
void create_num(int arr[])   //产生一个数组 从0~1023
{
    int i=0,n=1;
    for (;i<1024;i++)
    {
        n++;
        arr[i]=n;
    }
}

void half_find(int arr[],int num,int first_num,int last_num)
{   

    int half_num = (first_num + last_num)/2;

    if( arr[half_num] == num)
    {
        printf("find it!\n");
        return;
    }

    else if( arr[half_num] > num)
    {
        last_num=half_num-1;
        half_find(arr,num,first_num,last_num);  //递归
    }

    else if( arr[half_num] < num)
    {
        first_num=half_num+1;
        half_find(arr,num,first_num,last_num);  //递归
    }
}

void main()
{
    int arr[1024]={0};
    create_num(arr);
    half_find(arr,49,3,500);  //第二参数是要查找的数，第3、4个参数分别为上下边界。最好改成输入的形式，防止出现越界。
}