c 如何输出折半查找法比较次数
1、第一步先导入头文件,然后定义获取数组长度的函数,便于后面代码的引用
#include<stdio.h>
int a[100]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
//先假定一个有序数组,然后向其中插入一个数值,(如果数组无序,需要先排序,此处为有序的数组)
//令其自增规律不变,同时统计二分法比较次数
int get_length(const int *a)//返回字符串长度
{
int length=0,i=0;
while(*(a+i)!='\0')
{
i++;
length++;
}
return length;//此处返回16
}
2、第二步,因为数组经过二分法查找与修改,数组已经发生了变化,那么我们可以设定一个移位函数,让数组适应新的数据成员
void move_data(int station,int *a,int insert_data)//移动插入点后的数组数据,方便插入
{
int i=get_length(a)+1;
for(;i>=station;i--)
{
*(a+i+1)=*(a+i);
}
*(a+station)=insert_data;
}
3、第三部,这个是输出我们的新的数组的,为了使用方便,写成函数的形式
void pri_arr(int *a)//输出数组内的数据
{
int i=0;
printf("输出%d位数据\n",get_length(a));
while(*(a+i)!='\0')
{
printf("%d ",*(a+i));
i++;
}
}
4、第四步,进入主函数,写我们的二分算法
void main()
{
int num_insert,num_start,num_stop,station,i,num_count=0;
//插入的数据,二分法开始点,结束点,应该插入的位置,以及比较次数的计数变量
printf("请输入一个插入的数据:");
scanf("%d",&num_insert);
printf("数组长度为: %d\n",get_length(a));
num_start=0;
num_stop=get_length(a)-1;
if(num_insert<=a[num_start])//先判断极端情况
{
move_data(num_start,a,num_insert);
printf("小于最小的\n");
printf("找到的位置为%d\n",num_start);
num_count=1;
}
else if(num_insert>=a[num_stop])//先判断极端情况
{
printf("比较的数据为%d\n",a[num_stop]);
move_data(num_stop+1,a,num_insert);
printf("大于最大的\n");
printf("找到的位置为%d\n",num_stop+1);
num_count=1;
}
else
{
do{
i=(int)((num_start+num_stop)/2);
if(num_insert<=a[i]&&num_insert>=a[i-1])//找到插入点了
{
move_data(i,a,num_insert);
printf("找到的位置为%d\n",i);
num_count++;//开始计数
break;
}
else if(num_insert>a[i])
{
num_start=i;
num_count++;//开始计数
}
else
{
num_stop=i;
num_count++;//开始计数
}
}while(1);
}
pri_arr(a);
printf("\n比较的次数为:%d\n",num_count);//输出计数
}
