二分插入

本文主要是介绍二分插入，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思想：对于已排好序的数组，例如升序数组插入一个数字，把数组的上、下界下标做形参，方便递归，每次取中间的数与插入数进行比较，
     特别注意当插入数小于中间数这种情况，这种情况下，移动时下标应从中间值那个下标开始移起（就因为这儿我Wrong了好多次）


解题代码：
#include <stdio.h>
#define N 100000
void Input(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
}

void Maopao(int a[],int n)
{
    int i,j,temp;
    for(i=0;i<n-1;i++)
    {
        for(j=1;j<n;j++)
        {
            if(a[i]>a[j])    //升序选择
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

void Charu(int a[],int low,int high,int k,int n)    //二分插入
{
    int i,r,temp;
    if(low>high)
        return ;
    else
    {
        r=(low+high)/2;
        if(a[r]<k)
        {
            if(a[r]<=k&&a[r+1]>=k)
            {
                for(i=r+1;i<n+1;i++)
                {
                    temp=k;
                    k=a[i];
                    a[i]=temp;
                }
                return ;
            }
            return Charu(a,r,high,k,n);
        }
        if(a[r]>k)
        {
            if(a[r]>=k&&a[r-1]<=k)
            {
                for(i=r;i<n+1;i++)
                {
                    temp=k;
                    k=a[i];
                    a[i]=temp;
                }
                return ;
            }
            return Charu(a,low,r,k,n);
        }
        if(a[r]==k)
        {
            for(i=r+1;i<n+1;i++)
            {
                temp=k;
                k=a[i];
                a[i]=temp;
            }
            return ;
        }
    }
}


void Output(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
}

int main()
{
    int a[N],n,k;
    printf("请输入数据个数：\n");
    scanf("%d",&n);
    Input(a,n);
    Maopao(a,n);
    Output(a,n);
    printf("\n请输入插入的数据：\n");
    scanf("%d",&k);
    Charu(a,0,n,k,n);
    Output(a,n+1);
    return 0;
}

这篇关于二分插入的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---