Question

要求使用折半法的关于数组的C语言编写

有一个已按降序排列的数组中,现输入一个任意整数,要求使用折半法,按原来排序的规律将它们插入数组中...
假设原数组为a[10]={50.42.38.25.10.7.6.3.0}

我要可以运行的完整的编写程序~

回答经采纳即追加分数~~

Answer 1

#include <stdio.h>
#define N 10
int main(){
int i,a[20]={0};/*建个大小为20是保证足够大*/
int inputNum,temp1,temp2,temp;
for (i=0;i<N;i++) {
scanf("%d",&a[i]);
fflush(stdin);
}/*初始化输入你要的数据，fflush保证输入数据正确，每输入完一个数据回车*/
for(i=0;i<N;i++) printf(" %d ",a[i]);
printf("\n");
scanf("%d",&inputNum);
temp1=0;
temp2=N-1;
if(a[0]==a[N-1]) a[N]=inputNum;/*如果数组全都一样大，那么没有大小顺序，直接最后赋值 */
if(a[0]<a[N-1]){/*数组从小到大排列的情况 */
while(temp1<temp2-1){
temp=(temp1+temp2)/2;
if(inputNum<a[temp]) temp2=temp;
else temp1=temp;
}/*折半查找到temp1,temp2,有三种情况 */
if(inputNum>a[temp2]) temp=temp2+1;/*输入数最大，则输入数据位于最后 */
else if(inputNum<a[temp1]) temp = temp1;/*输入数最小，则输入为第一个 */
else temp =temp2;/*输入数占据temp2元素的位置 */
for(i=N;i>temp;i--) a[i]=a[i-1];/*temp后所有元素后移 */
a[temp]=inputNum; /*输入数据插入*/

}else{/*数组从大到小的情况 */
while(temp1<temp2-1){
temp=(temp1+temp2)/2;
if(inputNum>a[temp]) temp2=temp;
else temp1=temp;
}
if(inputNum<a[temp2]) temp=temp2+1;
else if(inputNum>a[temp1]) temp = temp1;
else temp =temp2;
for(i=N;i>temp;i--) a[i]=a[i-1];
a[temp]=inputNum;
}
for(i=0;i<=N;i++) printf(" %d ",a[i]);
getchar();
return 0;
}
假定数组从小到大，temp1,temp2是两个标识，会不断接近，最后形成temp1=temp2-1;最坏的情况就是我们输入的数最小，那么temp1=0,这个时候所有的数都要后移。如果我们输入的数最大，那么temp2=9,我们只需要最后令a[10]为我们输入的数。如果不是以上2种情况那么只需要把a[temp2]后的数后移，a[temp2]赋我们输入的数。

我这个算法并不是最优的。应该细节上可以改进.不过我这个程序包括了降序和升序情况，自动处理

Answer 2

int m[N] n[N+1]；\\数组长度n自己设
int t,i,low,high,mid;\\设置上下标志和参量
low=0;high=N-1;\\参量初始化
printf("please input the data：%d \n",t);\\输入插入数据
while (!(t<m[mid]&&t>m[mid+1]))\\插入条件
{mid=(low+high)/2;\\二分法查找
if (t>m[mid])
high=mid-1;
if(t<m[mid])
low=mid+1;
}
for(i=0,i<n+1,i++)\\插入另外的数组
{if (i<mid)
n[i]=m[i];
else n[i]=t;
if (i>mid)
n[i]=m[i+1]
}

Answer 3

//给你 一个折半查找的例子！
//数组都由你自己输入
#include <stdio.h>
#include <string.h>

int BinSearch(int list[],int n,int key)
{
int mid,low,high;
int midvalue;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
midvalue=list[mid];
if(key==midvalue)
return list[mid];
else if(key<midvalue)
high=mid-1;
else
low=mid+1;
}
return -1;
}

int main()
{
int a[10],i;
int midvalue;
char insert;
while(1)
{
printf("请输入10个数,中间以空格隔开: ");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
printf("请输入要查找的数: ");
scanf("%d",&midvalue);
midvalue=BinSearch(a,10,midvalue);
if(midvalue!=-1)
{
printf("%d\n",midvalue);
break;
}
else
{
printf("没有您要查找的信息,重新查找请按y,退出请按n或任意键退出!\n\n");
insert=getch();
if(insert=='y'||insert=='Y')
printf("重新输入,");
else
break;
}
}

system("pause");
}