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

目录
  • 一.前言
  • 二.二分查找法
    • 1.什么是二分查找法
    • 2.如何用c语言来实现二分查找法
  • 三.总结
  • 总结

一.前言

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

二.二分查找法

1.什么是二分查找法

二分查找法，又叫做折半查找法，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。就用刚刚的数组来说，我们想寻找'7'，很简单我们先用7和数组中间的数来比较大小，很明显7大于，所以我们缩小范围，从中间的右边开始继续取中间值，继续寻找，直到找到位置，这样一看找的次数少了很多，而且速度也快了不少。

2.如何用c语言来实现二分查找法

咱们来分析一下刚刚我说的找数字7的过程，首先我们需要数组的中间的数也就是中间数的下标值，那我们就需要直到数组第一个元素和最后一个元素的下标值，数组第一个元素下标值很明显是0，我们把他定义成left；这个最后一个元素的下标值我们就需要利用sizeof来计算,我们把他定义成rigth。然后两个相加，算出最中间的下标，我们把他定义为mid，和要找的数进行比较，假如大于要找的数那就从mid+1和right之间来继续刚刚的循环，假如小于要找的数那我们就从left和mid-1之间寻找。就这样一直循环，直到找到目标数为止。

代码的实现如下

void Findnum(int* arr, int key,int sz)//arr为目标数组，key为需要查找的数,sz为数组元素的大小
{//二分查找
	int  left = 0;//左边
	int right = sz-1;//右边
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (arr[mid] > key)
		{//说明key在arr[mid]和left之间
			right = mid - 1;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，对应的下标为:%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到\n");
	}
}

最后运行

三.总结

关于上面的过程，我们不难发现二分查找法虽然很快，但是有两个很明显的缺点，一个是他实现的条件必须是一个有序的数列，另外一个是他只能一次性找一个数而不是多个，这就让他有了很多局限性。二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为

log2o是毫无疑问的。

总结

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

赞 (0)

相关推荐

  • C语言二分查找算法及实现代码

    C语言二分查找算法及实现代码

    二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

  • 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语言二分查找

    目录 总结 我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找 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语言二分查找的简单应用

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

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

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

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

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

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

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

  • Python 语言实现六大查找算法

    Python 语言实现六大查找算法

    目录 一.顺序查找算法 二.折半查找算法 三.插补查找算法 四.哈希查找算法 五.分块查找算法 六.斐波那契查找算法 七.六种查找算法的时间复杂度 一.顺序查找算法 顺序查找又称为线性查找,是最简单的查找算法.这种算法就是按照数据的顺序一项一项逐个查找,所以不管数据顺序如何,都得从头到尾地遍历一次.顺序查找的优点就是数据在查找前,不需要对其进行任何处理(包括排序).缺点是查找速度慢,如果数据列的第一个数据就是想要查找的数据,则该算法查找速度为最快,只需查找一次即可:如果查找的数据是数据列的最后一

  • 详解C语言中二分查找的运用技巧

    详解C语言中二分查找的运用技巧

    目录 基础的二分查 查找左侧边界 查找右侧边界 二分查找问题分析 实例1: 爱吃香蕉的珂珂 实例2:运送包裹 前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素.查找第一个和目标值相等的元素.查找最后一个和目标值相等的元素 三种情况. 这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 . 本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • 使用PHP实现二分查找算法代码分享

    第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

  • php实现的二分查找算法示例

    本文实例讲述了php实现的二分查找算法.分享给大家供大家参考,具体如下: <?php $arr = array(4,58,11,34,88,45,32,54,63,78); function binary($arr,$bnum) { if(is_array($arr) && count($arr) > 0) { sort($arr); $start = 0; $end = count($arr)-1; $mid = -1; while($start <= $end) {

  • PHP二分查找算法示例【递归与非递归方法】

    本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • python实现二分查找算法

    二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中) 优

  • Java实现二分查找算法实例分析

    本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

随机推荐