嗨,欢迎来到异星球,我是小怪同志。这篇文章主要讲认识算法,请一起学习吧。
一、算法的标准
(1)正确性:正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期。
(2)易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。
(3)健壮性:算法对非法数据及操作有较好的反应和处理。例如:在人口信息管理系统中登记人的年龄时,若将18岁写成180岁,则系统就会提示出错误。
(4)高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。
(5)低存储性:低存储性是指算法所需的存储空间小、对于像手机、iPad,电脑等这样的嵌入式设备,算法如果占用空间过大,则无法运行。算法占用的空间大小被称为空间复杂度。
二、二分法
1.二分法
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
2.算法思路
(1)所谓的二分法也就是折半查法,通俗的说就是已知区间已经排过序了然后根据中间值把数据一分为二。
(2)根据所需要查找的目标数x,判断是在前部分查找还是在后部分查找。
(3)最后重复上述的步骤找到所需要的目标数x。
3.算法分析
假设有十个元素,前半段用begin代表,中间值用mid代表,后半段用end表示。目标数用x表示。
要找目标数为7也就是下标为6
begin为数组最小的下标
end为数组的最大的下标
Mid=(begin+end)/2(mid=(0+9)/2=4)
若查找大于arr【mid】则查找的区间为后半段下标为5~9进行查找
若查找小于arr【mid】则查找的区间为前半段下标为0~3进行查找
因找的目标数为7,mid的值下标4,所以目标数7的下标6>min值的下标4
因此是后半段,要查找的区间下标为5~9,进行第二轮比较。
因为目标数7大于6,所以begin=mid+1(begin=4+1=5)end是不变的(end=9)
Mid=(5+9)/2=7,所以目标数7的下标6<mid值的下标7,进行第三轮比较。
因为目标值7的下标6<min值的下标7,所以begin不变(begin=5),end=mid-1(end=7-1=6)
Mid=(5+6)/2=5,所以目标数7的下标6>min值的下标5,,进行第四轮比较。
那么begin=5+1=6,end不变(end=6),mid=(6+6)/2=6,就找到了目标数7
如果还没有找到目标值,那么begin就再加1,也就是begin>end,无法查找,循环结束。
4.具体代码
include<stdio.h>
int main(void)
{
//begin为前半段,mid为中间值,end为后半段,
n为十个有序数,x为输入的一个目标数
int begin,mid,end,n=10,x;
//有序数组
int arr[]={1,2,3,4,5,6,7,8,9,10};
//求数组的个数
int sz=sizeof(arr)/sizeof(arr[0]);
//提示输入一个数为x
printf("请输入一个数x:\n") ;
scanf("%d",&x);
//开始查找区间为整个数组
begin=0;
end=sz-1;
//循环条件
while(begin<=end)
{
//中间位置
mid=(begin+end)/2;
//所找元素小于中间元素
if(x<arr[mid])
{
//新查找区间为前半段,end前移
end=mid-1;
}
//所找元素大于中间元素
else if(x>arr[mid])
{
//新查找区间为后半段,begin后移
begin=mid+1;
}
else
{
printf("index is %d\n",mid);
break; //查找成功,终止循环
}
}
if(begin>end)
{
printf("Not Found\n");
//没有查找到,结果为Not Found
}
return 0;
}