【C语言】二分查找（折半查找）-创新互联
目录
前言
代码实现
实现原理
问题分析
演示
求区间端点
求中间元素下标
这个语句可以用图像来解释
中间元素的值与目标值进行比较
判断是否找到
总结
前言
查找在现实生活中运用很广泛，我们在运用数组进行查找时往往想到遍历查找，而数组分为有序数组和无序数组，遍历查找对于无序数组来说，是一种好方法，但对于有序数组来说，有些繁琐，我们想要一种针对有序数组的快速查找方法——二分查找
代码实现#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://6mz.cn/article/heheh.html