1.题目描述
有15个数按由大到小顺序放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出“无此数”
二.思路分析
- 记录数组中左边第一个元素的下标为left,记录数组右边第一个元素的下标为right,记录中间元素的下标为mid(mid = left+right)
- 当输入的数在a[mid]的左边时,将right改成mid-1,同时mid = (left+right)/2;当输入的数在a[mid]的右边时,将left改成mid+1,同时mid = (left+right)/2;
- 执行上面第2步,直到left>right时退出循环,退出也就意味着该数没在数组中
举个例子:
三.代码实现
#include <stdio.h>
int main()
{
int a[15] = { 101,99,94,89,84,80,79,77,74,73,70,23,13,9,1 };
int n = 0;
scanf("%d", &n);
int right = 14;
int left = 0;
int mid = (right + left) / 2;
while (left <= right)
{
if (n < a[mid])
{
left = mid + 1;
mid = (left + right) / 2;
}
else if (n > a[mid])
{
right = mid - 1;
mid = (left + right) / 2;
}
else
{
printf("该数为该数组中第%d个元素\n", mid + 1);
return 0;
}
}
if (left > right)
{
printf("无此数\n");
}
return 0;
}
代码修改自该博主->https://blog.csdn.net/yahid/article/details/123389973