C 二分查找算法
最编程
2024-07-07 10:16:34
...
前言
假如给你一组有序的数字,让你从中找出某个元素,我们可能首先想到的是利用循环从第一个元素开始试,直到找出来这个数或者没有找到循环结束。因为这样的方法查找次数比较多,耗费时间长。所以我们想到了另外一种比较节省时间且效率高的二分算法。
二分算法/折半查找算法
我们先说一下什么是二分算法,假如给出一个这样的一组有序数字1,2,3,4,5,6,7,8,9,10。让你从中找出数字7。我们先找出这组数字的中间数(5,6都可以),然后我们用这个中间数和我们要查找的数作比较,如果中间数大于我们要找的数,那我们就在这个数的右边找,即在6,7,8,9,10 中寻找。这样我们就把寻找范围缩小了一半,然后我们在用相同的方法找到中间数8,判断一下8>7,然后在8的左边找,这样范围就又小了一半变成了6,7,然后我们找6和7的中间数6, 6<7,我们把范围在缩小一半就只剩一个数7,然后判断这个数和7是否相等,如果不相等,就代表这个数组中没有我们要找的数字。
- 我们先把这几个数放进数组里面,然后定义数组得左右下标,然后利用数组元素的下标进行查找中间数和相关的操作。
int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
int left = 0;
int right = 9;
int mid;
- 判断中间元素与被查找值大小关系进行范围缩小
mid = (left + right) / 2; //计算中间元素下标
if (a[mid] > 7)
{
right = mid-1; //如果中间元素大于被查找数,就让原来的右下标变为现在的中间元素前一个数的下标
}
else if (a[mid] < 7)
{
left = mid+1; //如果中间元素小于被查找数,就让原来的左下标变为现在的中间元素后一个数的下标
}
else
{
printf("找到了下标为%d\n", mid);//这种情况就是中间元素刚好等于被查找数,我们就可以跳出循环了
break;
}
- 有的时候我们判断一两次判断不出来,就需要进行循环多次判断,直到范围精确到一个具体元素。
如果范围精确到一个具体元素还没有找到,就代表这个数组中没有我们要的数
while (left <= right)
{ //当范围缩小到left=right的时候,即范围精确到一个具体元素了,这个时候便是最后一次循环
mid = (left + right) / 2;
if (a[mid] > 1.5)
{
right = mid-1;
}
else if (a[mid] < 1.5)
{
left = mid+1;
}
else
{
printf("找到了下标为%d\n", mid);
break;
}
}
if (left > right) { //当left>right的时候,就是缩小最后一个元素也没有找到被查找数
printf("找不到");
}
return 0;
}
完整代码如下
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main(){
int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
int left = 0;
int right = 9;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (a[mid] > 1.5)
{
right = mid-1;
}
else if (a[mid] < 1.5)
{
left = mid+1;
}
else
{
printf("找到了下标为%d\n", mid);
break;
}
}
if (left > right)
{
printf("找不到");
}
return 0;
}
文中如有错误的地方,欢迎大家指正。
上一篇: 二进制搜索算法(二进制搜索)详解
推荐阅读
-
聚类分析 | IPOA 优化 FCM 模糊 C 均值聚类优化算法 - 基本介绍
-
华为 OD 机测试 - RSA 加密算法(Python/JS/C/C++ 2024 E 卷 100 分) - V.Python 算法源代码
-
算法 - 简单查找排序的 Python 实现
-
★ 算法 OJ 问题 ★ 二分查找算法
-
牛津大学每日一题_分组_枚举+二分法_C++_Java
-
C++ 算法学习 - 1.6 差分算法和二维差分算法
-
贪心算法c++
-
华为 OD 机测试 - Excel 单元格值统计(Python/JS/C/C++ 2024 年 E 卷 200 分) - VIII、C 算法源代码
-
(C 语言中的 Gluttony) 4. Gluttony 地图优化和算法说明
-
C++ 算法学习 - 1.3 拓扑排序