C语言折半查找法的由来及使用详解

目录
  • 引入二分查找
  • 分析二分查找
    • 计算中间下标的两种方法
      • 第一种
      • 第二种
  • 代码实现
  • 总结

引入二分查找

本文带着大家学习一个简单的**二分查找算法，也叫折半查找算法**

先给大家提出一个问题

额，大家应该都会碰到这种情况，那大家怎么猜呢？

我想一定是会说1000，他说太少了，你又猜1500…

这其实就是二分查找的应用。

接下来我们来看一个问题

如何在一个有序数组中查找一个数字？

有一部分帅气的观众可能会说:

直接遍历数组，一个一个对比就找到了啊

但是大家有没有想过一个问题，数组中如果只有几十个数的话，那完全可以这样做

那如果数组中有几十万个呢？

这样遍历绝对是非常消耗时间，题目很明确说有序数组，如果直接遍历，我们是不是对不起有序这二字呢？

分析二分查找

我们用一个简单的实例来实现一下二分查找

比如有这样一个数组

计算中间下标的两种方法

我们在其中查找一个数字。使用二分查找，我们如何确定中间值呢？

有人说，数组长度除以二，但是中间值会变，数组长度不可变 ----排除

这边我们给大家带来两种方法来计算中间值

首先大家要清楚，我们要有两个边界，就是范围，比如鞋子02000变成10002000

我们使用两个下标作为两端，left 以及 right 中间值我们定义为mid

第一种

mid = (left + right) / 2;

我对长度为奇数和偶数的数组都进行了分析，这种方法并没有漏过任何一个数，所以可以使用

第二种

第一种方法有一种弊病，如果数组特别长的话，left+right可能会超出类型的最大值范围

我们得想办法解决掉这个问题

假如我们把left最上边那一小块放到left上边，是不是就是中间值了呢

、

把这种方法写成表达式就是

mid = (right - left) / 2 + left;

这就是两种计算中间下标的方法

代码实现

  • 当mid处的值 < 待查找的值的时候 ，需要把 mid处的以及前边的舍弃,即left右移， left = mid +1;
  • 当mid处的值 > 待查找的值的时候 ，需要把 mid处的以及后边的舍弃,即right左移，right = mid -1;
  • 当相等时，便不再查找。

还有一个问题,什么时候就不再查找了呢？

  • left < right 时，中间仍有数据未查找
  • left = right 时，有一个数未比较
  • left>right 时，都找完了，没找到

所以当left > right 时，就没必要查找了

话不多说，直接上代码

#include <stdio.h>
//详解二分查找
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//计算数组长度
	int length = sizeof(arr) / sizeof(arr[0]);
	int n = 0;//待查找的值
	scanf("%d", &n);
	int left = 0;//左下标
	int right = length - 1;//右下标
	int mid = 0;//中间下标
	while(left <= right)
	{
		mid = (left + right) / 2;
		if(arr[mid] > n)
		{
			right = mid - 1;
		}
		else if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下标为%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到，数组中不存在该值\n");
	}
	return 0;
}

总结

理解二分查找法的实现方式

核心在于中间下标的控制以及下标的变化

大家下来一定要自己画图理解，写代码测试，多写写就悟了。

到此这篇关于C语言折半查找法的由来及使用详解的文章就介绍到这了,更多相关C语言折半查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数据结构之 折半查找实例详解

    C语言数据结构之 折半查找实例详解

    数据结构 折半查找 实例代码: /* 名称:折半查找 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define N 11 // 数据元素个数 typedef int KeyType; // 设关键字域为整型 typedef struct // 数据元素类型 { KeyType key; // 关键字域 int

  • C语言算法练习之折半查找的实现

    C语言算法练习之折半查找的实现

    目录 1. 题目描述 2. 问题分析 3. 算法设计 4. 动图演示 5. 代码实现 6.知识点补充 continue 语句 break 语句 continue语句 和 break语句的区别 7. 问题拓展 1. 题目描述 N 个有序整数数列已放在一维数组中,利用二分查找法查找整数 m 在数组中的位置. 若找到,则输出其下标值:反之,则输出 “ Not be found!”. 2. 问题分析 二分查找法(也叫折半查找)其本质是分治算法的一种. 所谓分治算法是指的分而治之,即将较大规模的问题分解成

  • C语言折半查找法的超详细讲解

    折半查找法仅适用于对已有顺序的数组.数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=(high+low)/2.注意:low,mid,high都要与下标绑定,也就是说它们就是下标.且循环条件是:high>=low. 同时注意:⑴若原来数组是由小到大排列的则:       mid=(high+low)/2;             if(key<a[mid])//说明要找的值在左边

  • C语言实现顺序表的顺序查找和折半查找

    本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include <iostream> using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放要查询的数 int i=n; while(r[i]!=k)//不用判断下标i是否越界 { i--; } return i; } int main() { int n; cout<<&quo

  • C语言实现折半查找法（二分法）

    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:折半查找法仅适用于对已有顺序的数组.数据进行操作!!! 很显然,折半查找法相对于其他查找方法例如顺序查找法效率要高很多: 下面我们来实际操作一下,了解二分查找的奥义. 例如:要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置:首先,我们要先将数组arr中的数据成员进行排序.arr[]={1,2,3,4,5,6,7,8,9,1

  • C语言算法--有序查找(折半查找/二分查找)

    目录 题目 解法一: 挨个遍历 方法二:折半查找/二分查找(仅适用于有序查找) 总结 题目 首先我们来把题目瞅一眼: 在一个有序数组中查找具体的某个数字n. 编写int binary_search (int x, int v[], int n); 功能:在v [0] <= v [1] <= v [2] <= -. <= v [n-1]的数组中查找x. 题目大概的意思就是说这是一串有序的数组,我们编写代码完成以下功能:如果输入的数字在数组中,就输出找到了并输出下标,如果输入的数字不在

  • 纯C语言:折半查找源码分享

    复制代码 代码如下: #include <stdio.h>       int bin_search(int key[],int low, int high,int k)      {        int mid;        if(low>high)    {       return -1;        }    else       {             mid = (low+high) / 2;             if(key[mid]==k)         

  • C语言折半查找法的由来及使用详解

    C语言折半查找法的由来及使用详解

    目录 引入二分查找 分析二分查找 计算中间下标的两种方法 第一种 第二种 代码实现 总结 引入二分查找 本文带着大家学习一个简单的**二分查找算法,也叫折半查找算法** 先给大家提出一个问题 额,大家应该都会碰到这种情况,那大家怎么猜呢? 我想一定是会说1000,他说太少了,你又猜1500… 这其实就是二分查找的应用. 接下来我们来看一个问题 如何在一个有序数组中查找一个数字? 有一部分帅气的观众可能会说: 直接遍历数组,一个一个对比就找到了啊 但是大家有没有想过一个问题,数组中如果只有几十个数

  • C语言折半查找法介绍及使用示例

    C语言折半查找法介绍及使用示例

    目录 1. 折半查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 折半查找介绍 1.1 定义 折半查找也称二分查找,是一种在有序数组中查找某一特定元素的搜索算法,每一次查找,搜索范围均缩小一半,效率较高.如果数组是乱序状态,则应排序,再进行查找. 1.2 基本原理 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中

  • Java利用泛型实现折半查找法

    Java利用泛型实现折半查找法

    目录 泛型化的折半查找法 1.题目 2.解题思路 3.代码详解 知识点补充 泛型化的折半查找法 1.题目 泛型是JAVA重要的特性,使用泛型编程,可以使代码复用率提高. 实现:查找作为泛型的一个简单应用,使用泛型实现折半查找法 2.解题思路 创建一个类:BinSearch. 折半查找要求数据集合中的元素必须可比较,并且各元素按升序或降序排列.取集合的中间元素作为比较对象,如: (1)如果给定的值与比较对象相等,则查找成功,返回中间元素的序号. (2)如果给定的值大于比较对象,则在中间元素的右半段

  • C语言常用库函数的使用及模拟实现详解例举

    目录 1.strlen 1.计数法 2.递归法 3.指针减指针 2.strcpy 3.strcmp 4.strcat 5.strstr 6.strtok 7.字符分类函数 8.memcpy&memmove 9.memcmp 经历了C语言基础篇的学习,让我们来简单了解几个C语言的库函数! 1.strlen 字符串已经 '\0' 作为结束标志,strlen函数返回的是在字符串中 '\0' 前面出现的字符个数(不包 含 '\0' ). 函数的模拟实现 1.计数法 int my_strlen(dest)

  • C语言预处理预编译命令及宏定义详解

    C语言预处理预编译命令及宏定义详解

    目录 程序翻译环境和执行环境 翻译环境:详解编译+链接 1. 编译 - 预处理/预编译 test.c ---- test.i 2. 编译 - 编译 test.i ---- test.s 3. 编译 - 汇编 test.s ---- test.obj 4. 链接 test.obj ---- test.exe 运行环境 预处理/预编译详解 #define 定义标识符 #和## #的作用 ##的作用 命名约定 命令行定义 条件编译 常见的条件编译指令 文件包含 offsetof(宏类型,成员名字)偏移

  • C语言*与&在操作线性表的作用详解

    在数据结构线性表一章,对线性表有这些操作方法(Operation): /*Operation*/ Initlist(*L);/*初始化操作,建立一个空的线性表L*/ ListEmpty(L):/*判断线性表是否为空表,若线性表为空,返回值为true,否则返回false*/ ClearList(*L):/*将线性表清空*/ GetElem(L,i,*e):/*性表L中的第i个位置元素值返回给e*/ LocateElem(L,e):/*在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在

  • C语言 风靡一时的黄金矿工游戏实现流程详解

    C语言 风靡一时的黄金矿工游戏实现流程详解

    游戏的玩法主要是通过不断采集地下的黄金和钻石,来得到更高的积分.只有完成任务目标,才可以通过相应的关卡.游戏画面中沙滩上的人物便是玩家的角色,下方深褐色的部分是地下,而黄金和钻石就是玩家需要采集的物品.人物右边的四个方框里的物品是游戏中可以使用的道具. 画面中的虚线就是游戏中的探测器,探测器会不断的左右摆动,当摆动到地下的黄金和钻石的位置时,只需要点击矿坑任意处,便可以发射勘探头采集到这些物品,当然一定要瞄准好再出手呦. 当然想要顺利采集到丰富的资源也不是那么简单的,地下矿坑中,会有各式各样的困

  • C语言静态与动态通讯录的实现流程详解

    目录 静态通讯录 contact.h contact.c test.c 动态通讯录 contact.h contact.c qsort.c test.c 本次通讯录的代码已经放到我的Gitee仓库中,感兴趣的小伙伴可以去看看 Gitee 静态通讯录 在我们学习完C语言的结构体.指针以及动态内存管理之后,我们就可以实现一些有意思的小项目了,通过这些小项目可以加深我们对于相关知识的理解. 静态通讯录主要要求有 静态大小,可以记录10个人的信息(大小自己定) 记录的信息如下:名字.性别.年龄.电话.住

随机推荐