【C语言】详解:折半查找(二分查找算法)
2023-09-11 14:17:48 时间
前言
当我们需要在一堆有序的数组中(二分查找只支持有序数组)找到某个元素的位置,即下标的时候,最常见的是遍历的方法(暴力求解法),一个个核对,不相等就跳到下一个,但是这种方法要浪费很多时间。这时候,我们就需要用到折半(二分)查找算法啦。
一、思路
那什么是折半(二分)查找算法呢?
我们先来看一个情景—猜数字游戏,数字的范围在1-100之间,我让你猜某个数字,那么聪明的你第一时间肯定会猜50,然后我告诉你猜小了,然后你接下来猜肯定在51-100之间猜75,我又告诉你猜大了,然后你继续像这样才直到猜出正确的数字,其实在这个猜数字的过程中,你用到的就是折半查找算法,那么我们需要用相同的逻辑用代码实现这个折半查找算法。
图解
开始时,left=0,right=9(为数组元素下标),现在你要折半找到中间元素,所以mid(middle是中间的意思)=(left+right)/2=4,下标为4的元素是5,5比7小,即arr[mid]<k,这时候你是不是就要从6-10中寻找呢?,所以这时候,left=mid+1,right则不变,因为没找到你要的元素,所以你继续折半查找,这时候mid=7,下标为7的元素是8,比k大,所以则时候范围缩小到6和7,下标分别为5,6,mid=5,arr[mid]=6,比k小,所以mid+1,这时候就找到k了,及时跳出循环。注意要用循环来实现,条件是left<=right.
二、代码的实现
#include<stdio.h>
int main()
{
//数组的下标从0开始
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 7;
//利用sizeof函数计算数组元素个数
int sz = sizeof(arr) / sizeof(arr[0]);//10
int left = 0;
int right = sz - 1;//元素10的下标为9
//循环的条件
while (left <= right)
{
int mid = left +(right - left)/2;//防止溢出
//int mid=(left+right)/2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid] > k)
{
right = mid - 1;
}
else
{
printf("找到k了,下标为:%d\n", mid);
break;//找打元素之和就赶紧退出循环,不然会陷入死循环的!
}
}
if (left > right)
{
printf("找不到\n");
}
return 0;
}
相关文章
- Btree算法的C语言实现
- C语言计算时间函数 & 理解linux time命令的输出中“real”“user”“sys”的真正含义
- C语言冒泡、选择、直插算法
- 《C语言编程初学者指南》一第1章 C编程入门
- 《C语言开发从入门到精通》一2.4 技术解惑
- 基于C语言实现(控制台)学生程序管理系统【100010764】
- 排序算法(C语言)
- 数据结构-图的实现以及基础算法-C语言实现
- Android JNI编程(四)——C语言多级指针、数组取值、从控制台输入数组
- C语言:预处理(2)
- 排序算法之选择排序【C语言】
- C++应该被看成是个语言集合——四种语言(C语言,OO语言,泛型语言,STL)
- 《数据结构与算法 C语言版》—— 2.2线性表的顺序表示与实现
- 《数据结构与算法 C语言版》—— 2.5上机实验
- 《数据结构与算法 C语言版》—— 3.4队列
- C语言基本输入输出程序设计——计算当前时间and转换大写姓名and工资信息表
- C语言基本语法入门练习题
- C语言之条件语句练习题
- 【嵌入式项目应用】__单片机ADC,常用的C语言滤波算法
- C语言100个经典的算法
- C语言之基本算法32—鞍点
- 常见算法:C语言求最小公倍数和最大公约数三种算法
- C语言------求字符串的长度,编写函数不允许创建临时变量