C语言折半查找怎么实现

蜗牛 互联网技术资讯 2022-05-07 25 0

本篇内容介绍了“C语言折半查找怎么实现”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

    1. 题目描述

    N 个有序整数数列已放在一维数组中,利用二分查找法查找整数 m 在数组中的位置。

    若找到,则输出其下标值;反之,则输出 “ Not be found!”。

    C语言折半查找怎么实现  c语言 第1张

    2. 问题分析

    二分查找法(也叫折半查找)其本质是分治算法的一种。

    所谓分治算法是指的分而治之,即将较大规模的问题分解成几个较小规模的问题,这些子问题互相独立且与原问题相同,通过对较小规模问题的求解达到对整个问题的求解。

    我们把将问题分解成两个较小问题求解的分治方法称为二分法。需要注意的是,二分查找法只适用于有序序列。

    二分查找的基本思想是:每次查找前先确定数组中待查的范围,假设指针 low 和 high (low<high) 分别指示待查范围的 下界 和 上界,指针 mid 指示区间的 中间位置,即 mid=(low+high)/2,把 m 与 中间位置 (mid) 中元素的值进行比较。

    如果m的值大于中间位置元素中的值,则下一次的查找范围放在中间位置之后的元素中;

    反之,下一次的查找范围放在中间位置之前的元素中。直到 low>high,查找结束。

    3. 算法设计

    N 个有序数应存放在数组中,根据数组下标的取值范围知指针 low 和 high 的初值分别为 0、N-1。

    除了三个指针变量 low、high、mid 之外还需要一个变量(假设为 k)来 记录下标,利用变量 k 的值来 判断整数是否在所给出的数组中。下面我们用示意图来表示二分查找的过程。

    假设一维数组中存储的有序数列为:5 13 19 21 37 56 64 75 80 88 92,要查找的整数 m 为 21。

    根据二分查找方法可知指针 low 和 high 最初分别指向元素 5 和 92,由 mid=(low+high)/2 知,指针 mid 指向元素 56。示意图如下:

    C语言折半查找怎么实现  c语言 第2张

    变量 m 所代表的整数 21 与 指针 mid 所指的元素 56 进行比较, 21 小于 56, 根据二分查找算法知, 查找范围现在缩小到指针 mid 所指元素的前面, 即从 5~37 的范围。

    指针 high 原来指向下标为 N-1 的元素,现在指向下标为 mid-1 的元素,接着重新计算指针 mid 所指元素的下标。

    C语言折半查找怎么实现  c语言 第3张

    再次进行比较,21 大于 19,现在比较范围再次转移到 mid 所指元素的后面,low 元素所指元素下标由 0 变为 mid+1。

    C语言折半查找怎么实现  c语言 第4张

    当前 mid 所指元素的值为 21,与要查找的整数值相同,因此查找成功,所查元素在表中序号等于指针 mid 的值。

    4. 动图演示

    动图解析

    C语言折半查找怎么实现  c语言 第5张

    5. 代码实现

    流程图设计

    完整代码

    #include <stdio.h>
    #define N 10
    
    int main()
    {
    	int a[N] = { -3,4,7,9,13,45,67,89,100,180 }; 
    	int low = 0; 
    	int high = N - 1; 
    	int mid; 
    	int i;
    	int m; 
    	int k = -1;
    
    	printf("a 数组中的数据如下:");
    	for (i = 0; i < N; i++)
    	{
    		printf("%d ", a[i]); 
    	}
    
    	printf("\n");
    
    	printf("Enter m:");
    	scanf("%d", &m); 
    
    	while (low <= high) 
    	{
    		mid = (low + high) / 2; 
    
    		if (m < a[mid])
    		{
    			high = mid - 1;
    		}
    		else
    		{
    			if (m > a[mid])
    			{
    				low = mid + 1;
    			}
    			else
    			{
    				k = mid;
    				break; 
    			}
    		}
    	}
    	if (k >= 0)
    		printf("m=%d index=%d\n", m, k);
    	else
    		printf("Not be found!\n");
    }

    运行结果

    C语言折半查找怎么实现  c语言 第6张

    C语言折半查找怎么实现  c语言 第7张

    代码贴图

    C语言折半查找怎么实现  c语言 第8张

    程序分析

    在上述程序中循环结束可以有两种情况。

    一种是由于循环的判定条件 low <= high 不成立的情况下跳出循环,此时可知查找不成功。

    在查找不成功的情况下,语句 else {k=mid; break;} 是不执行的,所以变量 k 的值不变仍为初值 -1。

    第二种结束循环的情况是由于执行了 break; 语句而跳出循环,在此情况下,变量 k 的值由 -1 变成了一个大于等于 0 的数,即指针 mid 所指元素的下标值。

    所以在最后用选择结构来判定 k 的值,从而确定整个查找过程是否成功。

    6.知识点补充

    continue 语句

    continue 语句的格式为:

    continue;

    continue 语句用于循环语句(while循环语句 或 do...while循环语句 或 for循环语句)中,作为循环体的一部分。

    在程序执行时,一旦遇到了 continue 语句,则立即结束本次循环,即跳过循环体中 continue 后面尚未执行的语句,接着进行是否继续循环的条件判定。

    break 语句

    break 语句的格式如下:

    break;

    break 语句 可用在 switch 语句中。

    在程序执行时, 一旦遇到了 break 语句, 则立即退出当前的 switch 语句。

    除此之外, break 语句还能用于循环语句(while循环语句 或 do...while 循环语句 或 for 循环语句))中, 作为循环体的一部分。

    在程序执行时, 一旦遇到了 break语句, 则立即退出当前的循环体,接着执行当前循环体下面的语句。

    continue语句 和 break语句的区别

    continue 只是结束本次循环,不再执行循环体中 continue 后面的其余语句,并不是终止当前循环。

    break 是直接终止当前的循环。

    7. 问题拓展

    在一个给定的数据结构中查找某个指定的元素,通常根据不同的数据结构,应采用不同的查找方法。对于一个有序数列,除了采用二分查找法之外还可以采用 顺序查找 的方法。

    顺序查找一般是指 在线性表中查找指定的元素,其基本方法如下:

    从线性表的第一个元素开始,依次将线性表的元素与被查元素进行比较,若相等则表示找到即查找成功;

    若线性表中所有的元素都与被查元素进行了比较但都不相等,则表示线性表中没有要找的元素即查找失败。

    在长度为 n 的线性表中查找指定元素,最好的情况是比较一次成功,最坏的情况是比较 n 次,平均要比较(1+2+3+&sdot;&sdot;&sdot;+n)/n=(1+n)/2 次。

    尽管顺序查找的效率低,但对于一些情况只能采用顺序查找的方法,如对于一个无序表进行查找。

    完整代码

    #include <stdio.h>
    #define N 10
    
    int main()
    {
    	int a[N] = { -3,4,7,9,13,45,67,89,100,180 }, i, m, k = -1;
    	printf("a数组中的数据如下: ");
    	for (i = 0; i < N; i++)
    	{
    		printf("%d ", a[i]); //输出数组中原数据序列
    	}
    
    	printf("\n");
    
    	printf("Enter m: ");
    	scanf("%d", &m); //由键盘输入要查找的整数值
    
    	for (i = 0; i < N; i++)
    	{
    		if (m == a[i])
    		{
    			k = i;
    			break; //一旦找到所要查找的元素便跳出循环
    		}
    	}
    
    	if (k >= 0)
    		printf("%m=%d index=%d\n", m, k);
    	else
    		printf("Not be found!\n");
    
    	return 0;
    }

    运行结果

    C语言折半查找怎么实现  c语言 第9张

    C语言折半查找怎么实现  c语言 第10张

    “C语言折半查找怎么实现”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注蜗牛博客网站,小编将为大家输出更多高质量的实用文章!

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:niceseo99@gmail.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    评论