【C语言】二分查找(折半查找)-创新互联
目录
创新互联建站从2013年开始,先为阿克陶等服务建站,阿克陶等地企业,进行企业商务咨询服务。为阿克陶企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。前言
代码实现
实现原理
问题分析
演示
求区间端点
求中间元素下标
这个语句可以用图像来解释
中间元素的值与目标值进行比较
判断是否找到
总结
前言
查找在现实生活中运用很广泛,我们在运用数组进行查找时往往想到遍历查找,而数组分为有序数组和无序数组,遍历查找对于无序数组来说,是一种好方法,但对于有序数组来说,有些繁琐,我们想要一种针对有序数组的快速查找方法——二分查找
代码实现#define _CRT_SECURE_NO_WARNINGS
#includeint main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
//数组的元素个数(因为定义时并未明确给出)
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz-1;
int num = 0;
int mid = 0;
int flag = 0;
int ret = 0;
printf("请输入要查找的数^v^\n");
scanf("%d", &num);
//查找
while (left<= right)
{
mid = left + ((right - left) / 2);
if (arr[mid] == num)
{
flag++;
ret = mid;
printf("这个数下标为:");
break;
}
else if (arr[mid] >num)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
//显示是否找到
if (flag == 0)
{
printf("找不到QAQ\n");
}
else
{
printf("%d", ret);
}
return 0;
}
实现原理
问题分析我们在数学中学过二分法,以猜车辆价格为例,价格给定范围是1w~100w,车辆价格为62.5w,我们在1w~100w之间进行猜测,先猜50w,车主说猜小了,然后再在50w~100w之间猜,猜75w,车主说猜大了,再在50w~75w之间猜测,我们猜62.5w,车主说猜对了。
由此可知,利用二分法进行查找,首先要知道区间两端的值,这样才能得出中间值,再用中间值与答案进行比较,小了就变动左端点,大了就变动右端点。
演示数组arr中存放有1~15数字,我们将在这个范围进行查找。
求区间端点要求中间下标的值,首先要确定首尾元素的下标left和right
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz-1;
求中间元素下标我们先求中间下标的值。
mid = left + ((right - left) / 2);
为什么不是收尾元素的和除以2呢?假设left和right都在某数据类型范围之内,当right接近于该数据类型的临界值时,right+left会超出该数据类型的范围,存的数并不是理想的数。
这个语句可以用图像来解释有两根不同长度的木棒,我们想求出他们的平均长度
先求出差值
再将差值除以2,平均分配给两根木棒
现在我们便的到了两根相同长度的木棒,它的长度便是平均长度。
中间元素的值与目标值进行比较如果中间值小于目标值,调整左端点left的值。
如果中间值大于目标值,调成右端点right的值。
利用while循环,直到左端点大于等于右端点时,结束比较。同时用flag作为标志器,找到了就自增一下,若是循环结束都没找到,flag就为零。
while (left<= right)
{
mid = left + ((right - left) / 2);
if (arr[mid] == num)
{
flag++;
ret = mid;
printf("这个数下标为:");
break;
}
else if (arr[mid] >num)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
判断是否找到 //显示是否找到
if (flag == 0)
{
printf("找不到QAQ\n");
}
else
{
printf("%d", ret);
}
总结 二分查找的前提条件是有序!二分查找的思路是,求端点的下标——》求中间值的下标——》与目标进行比较——》中间值大于目标就调整右端点下标,中间值小于目标就调整左端点下标。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站栏目:【C语言】二分查找(折半查找)-创新互联
链接URL:http://ybzwz.com/article/heheh.html