C语言数据结构之二分法查找详解

问题：在有序数组中查找给定元素的下标goal。

在查找一个数组元素的下标，可以用循环来解决，但是如果一个数足够大，比如说手机的价格，用循环来查找，就相当于叫一个人猜，从0开始，需要猜很久。这时候就出现了二分查找，也叫对半查找。

对半查找顾名思义就是猜一次，下次猜的内容就减少一半             

这时候定义一个变量left表示最左边元素的下标，在定义一个right表示最右边元素的下标，而mid就表示中间元素的下标。

当中间值小于目标值，left重新定义。

if (mid < goal)
		{
			left = mid + 1;
		}

当中间值大于目标元素，right重新定义。

else if (mid > goal)
		{
			right = mid - 1;
		}

当中间元素等于目标元素时，打印即可。

else
		{
			printf("你找到了，下标为：%d", mid);
			break;
		}

这中查找方式可能会使用多次，这时候来一个while循环就可以重复查找的撒

如果最后数组元素找不到对应的元素，就在while循环外打印出找不到。

	if (left > right)
		printf("找不到");

最后代码如下：

#include<stdio.h>//在数组中找到某个数,二分查找
int main()
{
	int goal = 7;
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof arr[0];
	int left = 0; int right = sz - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (mid < goal)
		{
			left = mid + 1;
		}

		else if (mid > goal)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标为：%d", mid);
			break;
		}
	}
	if (left > right)
		printf("找不到");
	return 0;
}

到此这篇关于C语言数据结构之二分法查找详解的文章就介绍到这了,更多相关C语言 二分法查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言基础之二分查找知识最全汇总

    C语言基础之二分查找知识最全汇总

    一.前言 在自学二分查找的过程中我想到了一些变化问题,有的自己就慢慢理解了,有的在网上找到了答案,奈何没有找到想要的总结归纳.我就斗胆自己写了一篇,号称史上最全.希望和我一样的伙伴可以少走一点弯路. 二分查找凭借其低时间复杂度O(log(n))成为了各个蒟蒻的入门知识,但是其衍生出的各种题目相较原题目而言就没有那么容易求解,以下借用c语言实现二分查找算法及其衍生.二分查找仅适用于事先已经排好序的顺序表.其基本思路就是每次取中间数,如果中间数大于所求数就向上查找,反之向下. 二.原始二分查找 1.

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • C语言二分法求解方程根的两种方法

    本文实例为大家分享了C语言二分法求解方程根的具体代码,供大家参考,具体内容如下 对于二分法求根,其实和弦截法思想很像,甚至更简单. 原理:先看如下的图 A,B两个点为跟的一个边界,通过一直缩小跟的边界,从而获取跟的值. (1)知道函数(即方程的式子),这个好说,题上都有 (2)循环的输入A,B的横坐标的值,即x1,x2的初值,直到f(x1)与f(x2)的乘积为负数才停止.(必须保证方程的跟在(x1,x2)区间)这样的x1,x2的初值才有意义. (3)令xx=(x1+x2)/2;(即中值),若f(

  • 一篇文章带你了解C语言二分查找

    一篇文章带你了解C语言二分查找

    目录 总结 我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找 int main() { int i, k = 0; scanf("%d", &k); int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < sz; i++) { if (arr[i] == k) { printf("

  • C语言编程之初识数组线性查找和二分查找

    C语言编程之初识数组线性查找和二分查找

    目录 线性查找 二分查找 先来了解一下什么是查找, 额,好吧,这没什么可了解的, 就是查找数组中的某个元素的位置或是否存在. 就这,没了.直接了解查找算法吧. 线性查找 线性查找与二分查找有些差别. 数组内元素可以是混乱无序的,即没有按顺序储存.这方法很简单,就是从首元素开始,依此向后查找,比较.仅此而已.运用循环,依次对比. 看代码吧. #include <stdio.h> int main(void) { int arr[] = { 5,4,6,8,7,9,10,2,3,1 }; int

  • 一篇文章带你了解C语言二分查找的简单应用

    一篇文章带你了解C语言二分查找的简单应用

    目录 前言 实战演练 思路分析 总结 前言 在有序数组中查找具体的某个数字n,可能有同学会说一个一个找,但是这样的效率实在太低,特别是对于有序的数组,效率太低.我们一般从中间元素开始找,查一次去掉一半数字,这种方法我们给它取名为折半查找即为二分查找,效率大大提高!怎么理解呢?如果有2的32次方个数字,我们最多只需查找32次,而一个一个数运气不好却是2的32次方次. 实战演练 这里我们先给出所写代码以及运行结果 在这里,给大家分析一下,首先,我们先创建一个有序数组arr[],然后我们把要查找的7用

  • 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语言巧用二分查找实现猜数游戏

    C语言巧用二分查找实现猜数游戏

    目录 (壹)二分查找   1.1  何为二分查找   1.2  二分查找的原理   1.3  查找条件   1.4  代码实现 1.4.1  初始化数据 1.4.2  核心函数 (贰)猜数字游戏   2.1  菜单初始化   2.2  核心函数   2.3  main函数   2.4  总代码 文章Gitee仓库:文章源代码 (壹)二分查找   1.1  何为二分查找 折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高.但是该算法的使用的前提是静态查找表中的数据必须是

  • 用C语言实现二分查找算法

    用C语言实现二分查找算法

    目录 一.前言 二.二分查找法 1.什么是二分查找法 2.如何用c语言来实现二分查找法 三.总结 总结 一.前言 假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来说,假如我们想寻找'2',那很简单我们只用从小到大开始寻找,寻找两次就完成了,但是我们想寻找'7',我们继续用从小到大挨个寻找,这就显得有点慢并且耗时长还没有效率,因此我们可以有一种全新的方法,二分查找法来解决这个问题. 二.二分查找法 1.什么是二分查找法

  • C语言数据结构之二分法查找详解

    问题:在有序数组中查找给定元素的下标goal. 在查找一个数组元素的下标,可以用循环来解决,但是如果一个数足够大,比如说手机的价格,用循环来查找,就相当于叫一个人猜,从0开始,需要猜很久.这时候就出现了二分查找,也叫对半查找. 对半查找顾名思义就是猜一次,下次猜的内容就减少一半              这时候定义一个变量left表示最左边元素的下标,在定义一个right表示最右边元素的下标,而mid就表示中间元素的下标. 当中间值小于目标值,left重新定义. if (mid < goal)

  • C语言数据结构哈希表详解

    C语言数据结构哈希表详解

    /* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • Go语言数据结构之插入排序示例详解

    Go语言数据结构之插入排序示例详解

    目录 插入排序 动画演示 Go 代码实现 总结 插入排序 插入排序,英文名(insertion sort)是一种简单且有效的比较排序算法. 思想: 在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置.重复该过程,直到所有输入元素都被选择一次,排序结束. 插入排序有点像小时候我们抓扑克牌的方式,如果抓起一张牌,我们放在手里:抓起第二张的时候,会跟手里的第一张牌进行比较,比手里的第一张牌小放在左边,否则,放在右边. 因此,对所有的牌重复这样的操作,所以每一次都是插

  • Go语言数据结构之二叉树可视化详解

    Go语言数据结构之二叉树可视化详解

    目录 题目 源代码 做题思路 扩展 左右并列展示 上下并列展示 总结回顾 题目 以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树:3.14*r²*h/3 源代码 package main import ( "fmt" "io" "os" "os/exec" "strconv" "strings" ) type any = interface{} type btNode struc

  • C语言数据结构之队列算法详解

    C语言数据结构之队列算法详解

    目录 一.前言 二.基本概念 三.顺序队列 四.链队列 五.循环队列 六.总结与提高 一.前言 队列在程序设计中经常出现,如:操作系统中的排队问题. 这篇文章主要介绍了队列的基本概念.性质,顺序.链.循环三种不同的方法实现队列,顺序和循环队列在算法中比较常用 二.基本概念    定义:队列是允许在一端插入,另一端删除的线性表 队头(front):允许删除的一端 队尾(rear):允许插入的一端 特点:先进先出 三.顺序队列 动态图: 算法讲解:  图解:入队,rear++,出队,front++

  • Python真题案例之二分法查找详解

    目录 写在前面的话

  • 用C语言递归实现火车调度算法详解

    用C语言递归实现火车调度算法详解

    目录 1.代码 2.代码详解 3.用二叉树表示调用过程 4.思维导图 笔者在李云清版的<数据结构>中第二章遇到了这道经典的火车调度题,经过对一些前辈的代码进行学习,以下将这段火车代码进行分析详解,不对之处,还请各位大佬指示,不胜感激! 1.代码 题目如下: 2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站,可能得到的调度结果有哪些?如果有n列火车通过调度站,请设计一个算法,输出所有可能的调度结果. 算法运用的思想是运用栈+递归,算法的难点也在于此.先上代码: #include &l

  • C语言 指针与数组的详解及区别

    C语言 指针与数组的详解及对比 通俗理解数组指针和指针数组 数组指针: eg:int( *arr)[10]; 数组指针通俗理解就是这个数组作为指针,指向某一个变量. 指针数组: eg:int*arr[10]; 指针数组简言之就是存放指针的数组: --数组并非指针&&指针并非数组 (1)定义一个外部变量: eg:int value=10; int *p=&value; 举例:当需要在一个函数中用这个变量时:externa int*p;而非extern int p[]; 分析:当用:e

  • 数据结构 红黑树的详解

    数据结构 红黑树的详解

    数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树: 1.每一个节点或者着红色,或者着黑色. 2.根是黑色的. 3.如果一个节点是红色的,那么它的子节点必须是黑色. 4.从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点. 下面是一棵红黑树. 1.自底向上插入 通常把新项作为树叶放到树中.如果我们把该项涂成黑色,那么违反条件4,因为将会建立一条更长的黑节点路径.因此这一项必须涂成红色.如果它的父节点是黑色的,插入完成.如果父节点是红色的,那么违反条件3.在这种情况下我们

随机推荐