这篇文章给大家分享的是有关C语言如何使用二分查找实现猜数游戏的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。(壹)二分查找 1.1 何为二分查找折半查找,也称二分查找,在某些情况下相比于顺序查
这篇文章给大家分享的是有关C语言如何使用二分查找实现猜数游戏的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。
例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先对该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}。
以升序数列为例,比较一个元素与数列中的中间位置的元素的大小,如果比中间位置的元素大,则继续在后半部分的数列中进行二分查找;如果比中间位置的元素小,则在数列的前半部分进行比较;如果相等,则找到了元素的位置。每次比较的数列长度都会是之前数列的一半,直到找到相等元素的位置或者最终没有找到要找的元素。
动图演示:(于顺序查找相比较)
查找到返回该元素的下标,否则返回-1。
普通查找的时间复杂度为O(N), 二分查找的时间复杂度为O(logN)。 N/2/2···/2=1,2^m=N(m为折半查找的次数),那么m=log(N),二分查找的时间复杂度就为O(logN)。
#include <stdio.h>#include <time.h>#include <stdlib.h>void menu(){printf("**********************************\n");printf("*********** 1.play ***********\n");printf("*********** 0.exit ***********\n");printf("**********************************\n");} //RAND_MAX--rand函数能返回随机数的最大值。void game(){int random_num = rand() % 100 + 1;int input = 0;while (1){printf("请输入猜的数字>:");scanf("%d", &input);if (input > random_num){printf("猜大了\n");}else if (input < random_num){printf("猜小了\n");}else{printf("恭喜你,猜对了\n"); break;}}} int main(){int input = 0;srand((unsigned)time(NULL));do{menu();printf("请选择>:");scanf("%d", &input);switch (input){case 1:game();break;case 0:break;default:printf("选择错误,请重新输入!\n");break;}} while (input);return 0;}
感谢各位的阅读!关于“C语言如何使用二分查找实现猜数游戏”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
--结束END--
本文标题: C语言如何使用二分查找实现猜数游戏
本文链接: https://www.lsjlt.com/news/322120.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0