C语言算法--有序查找(折半查找/二分查找)
时间：2022-02-27 09:20:57|栏目：C代码|点击： 次
题目
首先我们来把题目瞅一眼：
在一个有序数组中查找具体的某个数字n。
编写int binary_search (int x, int v[], int n);
功能：在v [0] <= v [1] <= v [2] <= …. <= v [n-1]的数组中查找x.
题目大概的意思就是说这是一串有序的数组，我们编写代码完成以下功能：如果输入的数字在数组中，就输出找到了并输出下标，如果输入的数字不在数组中则输出找不到。
下面看解法：
解法一： 挨个遍历
#include <stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//查找7
//遍历 0 ~ sz - 1
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int flag = 0;//0表示没有找到
for (i = 0; i < sz; i++)
{
if(7 == arr[i])
{
flag = 1;
break;
}
}
if (1 == flag)
printf("找到了，下标是：%d\n", i);
else
printf("没找到\n");
return 0;
}
博主这里的代码为了让大家可以看的更清楚，所以没有写成输入的模式，而是直接想要查找7。
这是万能的方法，就挨个遍历，有就是有，没有就是没有，属实牛批，但缺点是太费时间，如果要查找1 - 10000000中的10000000，那未免也太久了，既然这样的数组是一串有序的数组，不妨我们可以试试二分查找/折半查找。
方法二：折半查找/二分查找（仅适用于有序查找）
方法分析：
下面分析一下折半查找是怎么实现的，比如我们的数组是1 - 10，想要查找的数是7，那我们知道下标为0的数组对于1，下标为9的数组对于10，那我们则应该先找到中间下标对应的元素arr[mid]，让他和7比较，如果比7大，则将最右边的下标赋值为mid - 1，反之，则将最左边下标赋值为mid + 1，这样循环往复无限逼近要查找的数，每次排查一半，直到arr[mid] == 7，就找到了，如果直到最左下标和最右下标重合之后都找不到，那这个数一定不在这个有序数组内。
下面我们看代码是怎么写的：
代码实现：
#include <stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//查找7
//0 ~ sz - 1
int sz = sizeof (arr) / sizeof (arr[0]);
int left = 0;
int right = sz - 1;
int mid = 0;
int k = 7;//要查找的元素
int flag = 0;
while(left <= right) // 即使是 left == right,也有一个元素需要被查找
{
//求中间元素下标
mid = (left + right) / 2; // 每一次二分查找都要求出新的中间元素下标
if(arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid] > k)
{
right = mid - 1;
}
else
{
//找到了
flag = 1;
break;
}
}
if (1 == flag)
printf("找到了，下标是：%d\n", mid);
else
printf("找不到\n");
return 0;
}
虽然折半查找看起来代码比遍历查找多一些，但其实中间省了非常多计算机计算的时间，非常好用~~
总结
栏 目：C代码
本文地址：http://www.codeinn.net/misctech/194643.html
