C语言入门问题,下面是我写的代码,求大家帮忙看看哪里不对导致运行没有结果
循环中不要修改i的值。
不要修改i的值,while循环里面新建一个j来代替就好了
我们这里要求在一个有序的数组里找一个数字,利用C语言的方法最普遍的方法就是从后往前直找或者是从后往前找,那么,如果有100个数呢,1000个数呢,10000个数呢,你需要找多久呢?
在现实生活中,比如我买了一双鞋,你好奇问我多少钱,我说不超过300元。你还是好奇,你想知道到底多少,我就让你猜,你会怎么猜?
当然是每次从猜中间数。
我们怎么利用C语言来实现这个算法呢?
首先我们创建一个数组,在里面找一个数怎么表达?当然是数组的下标,然后通过下标实现这种算法,叫做折半查找法。
例如:
#include <stdio.h>
int main()
{
int arr[] = {1,2,3,4,5,6,7,8,9,10};//创建数组
int left = 0;//数组最左边的下标
int right = sizeof(arr)/sizeof(arr[0])-1;//数组最右边的下标,减一前面算的是数组的大小,原理是数组的长度除以数组里面第一个元素的长度
int key = 7;//要查找的数
int mid = 0;//两个数组下标和的平均数,也是二分查找的核心
while(left<=right)//判断条件是因为左下标和右下标如果跑到了相反的方向,就说明数组中没有这个数
{
mid = (left+right)/2;//这是查找的中间数
if(arr[mid]>key)//重新定义要查找的范围
{
right = mid-1;
}
else if(arr[mid] < key)//重新定义要查找的范围
{
left = mid+1;
}
else
break;//这个地方代表是找到了
}
if(left <= right)
printf("找到了,下标是%d\n", mid);//打印要查找数的下标
else
printf("找不到\n");
}
因为查找是一个重复动作,所以利用while循环。
这个代码看起来有些抽象,我画个图给大家看看!
这里,红色是数组的下标,然后紫色的是最左边的下标,褐色的是最右边的下标,蓝色的变量left和变量right相加和的一半的下标变量mid,这个变量也是用于锁定你要查找数的量,如果mid等于你要找的数的下标,说明找到了。
我们要找的是7这个数字,下标是6,第一次mid为4,它对应的是数组里面的5,5小于7所以我们查找的范围就变成了下标5到下标9之间,因为i虽然mid等于4,可是我们排查mid下标对应的数小于要查找的数,所以说mid对应下标的数一定不是要查找的范围,所以需要加一。
然后就变成了这个样子。这次我们找到了下标为7的元素,发现大于要查找的元素,所以范围缩小到了:
这里要强调一下,因为分为浮点数和整数,储存方式也不一样,下标是整形,两个数的和除以2的结果会把小数点后面的几位给丢掉,也就是(5+6)/2=5。
这次是小了,继续再找:
这次终于找到了,下标为6。
打印结果是:
找到了,下标是6
这次大家也可以明白为什么是这样一个查找范围,如果left到了right的右边,数组里面没有我们要查找的数。
这就是二分查找法C语言的实现。