那不就是二分法?每次比较后设置一个变量自增一下就好了.我举个栗子
工具/原料
vc++6.0或者c#任意可以编写c语言的软件,我用的vc
方法/步骤
1、第一步先导入头文件,然后定义获取数组长度的函数,便于后面代码的引用#include<衡痕贤伎stdio.h>inta[100]={吭稿荔徊1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};//先假定一个有序数组,然后向其中插入一个数值,(如果数组无序,需要先排序,此处为有序的数组)//令其自增规律不变,同时统计二分法比较次数intget_length(constint*a)//返回字符串长度{ intlength=0,i=0; while(*(a+i)!='\0') { i++; length++; } returnlength;//此处返回16}
2、第二步,因为数组经过二分法查找与修改,数组已经发生了变化,那么我们可以设定一个移位函数,让数组适应新的数据成员voidmove_data(intstation,int*a,intinsert_data)//移动插入点后的数组数据,方便插入{ inti=get_length(a)+1; for(;i>=station;i--) { *(a+i+1)=*(a+i); } *(a+station)=insert_data;}
3、第三部,这个是输出我们的新的数组的,为了使用方便,写成函数的形式voidpri_arr(int*a)//输出数组内的数据{ inti=0; printf("输出%d位数据\n",get_length(a)); while(*(a+i)!='\0') { printf("%d",*(a+i)); i++; }}
4、第四步,进入主函数,写我们的二分算法voidmain(){ intnum_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; } elseif(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; } elseif(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);//输出计数}
