数组07 – 零基础入门学习C语言29
第六章:数组07
让编程改变世界
Change the world by program
二维数组程序举例 — 二分法举例
假设在数组a中的数据是按由小到大顺序排列的:
-12 0 6 16 23 56 80 100 110 115,从键盘上输入一个数,判定该数是否在数组中,若在,输出所在序号。
TIPS:
第一步:设low、mid和high三个变量,分别指示数列中的起始元素、中间元素与最后一个元素位置, 其初始值为low=0,high=9,mid=4,判断mid指示的数是否为所求,mid指示的数是23,不是要找的80,须继续进行查找。
二分法原理
第二步:确定新的查找区间。因为80大于23,所以查找范围可以缩小为23后面的数,新的查找区间为[56 80 100 110 115 ],low,mid,high分别指向新区间的开始、中间与最后一个数。实际上high不变,将low(low=mid+1)指向56,mid (mid=(low+high)/2)指向100,还不是要找的80,仍须继续查找。
二分法原理
第三步:上一步中,所找数80比mid指示的100小,可知新的查找区间为[56 80],low不变,mid与high的值作相应修改。mid指示的数为56,还要继续查找。
二分法原理
第四步:根据上一步的结果,80大于mid指示的数56,可确定新的查找区间为[80],此时,low与high都指向80,mid亦指向80,即找到了80,到此为止,查找过程完成。
二分法原理
注意:若在查找过程中,出现low > high的情况,则说明,序列中没有该数,亦结束查找过程。
代码清单:
define M 10
include
void main()
{
static int a[M] = {-12,0,6,16,23,56,80,100,110,115};
int n, low, mid, high, found;
low=0;
high=M-1;
found=0;
printf("Input a number to be searched:");
scanf("%d", &n);
//以上进行一系列预处理……
while(low a[mid])
low=mid+1;
else
high=mid-1;
}
if(found == 1)
printf("The index of %d is %d",n,mid);
else
printf("There is not %d",n);
}
视频下载
技术, IT技术, 视频教程, C语言