自建免费网站,百度推广开户2400,用vs做的网站怎么打开,wpdx主题wordpress本期介绍#x1f356; 主要介绍#xff1a;二分查找的简单思路#xff0c;为什么必须在有序的前提下才能使用二分查找#xff0c;该怎么用C程序来实现二分查找#xff0c;二分查找的局限性#x1f440;。 文章目录 1. 题目2. 思路3. 前提条件4. 编写程序 1. 题目 在一个有…
本期介绍 主要介绍二分查找的简单思路为什么必须在有序的前提下才能使用二分查找该怎么用C程序来实现二分查找二分查找的局限性。 文章目录 1. 题目2. 思路3. 前提条件4. 编写程序 1. 题目 在一个有序的数组中查找一个数如果找到该数则返回下标如果没有找到就返回没有找到。 2. 思路 当我们要从一个序列中查找一个元素的时候最快想到的方法就是顺序查找法即从前到后依次查找。但这种方法过于无脑就是暴力的把每个元素都排查一遍。元素个数少的时候还行一旦元素个数多起来效率是非常低下所以在实际中这种查找的方法是被摒弃的。 这里就不得不介绍一种简单且效率较高的查找方法了二分查找法又称折半查找法。但该方法是建立在有序的前提下的基本思路就是先找到那个有序序列的中间元素mid然后拿它和要找的元素K进行比较就可以初步判断K所在范围既然查找范围已确定自然该范围之外的元素就可以不用再查找了。 因为二分查找每一次查找都可以缩减掉一半的查找范围由此可以知道二分查找法的时间复杂度: log 2 ( N ) \log_2(N) log2(N)。举个例子来解释该时间复杂度若这里一共有2^32个元素那么我在最坏的情况下也只需要32次就可以找到我想找的元素而顺序查找法最坏的情况下却需要查找 4,294,967,296 次可见二分查找法的效率是非常之高的。 3. 前提条件 都说二分查找法的前提条件是查找的序列必须是有序的。我想大概很多小伙伴都会错误的认为有序是差值恒为1的顺序数列就像这样1、2、3、4、5、6、7、8、9。这只不过是有序的某一种情况罢了那何为有序呢即该序列中的所有元素都是按照升序或者降序排列好的元素与元素只间的差值虽然是随机的但始终是在递增或递减例如这样一个序列3、12、24、31、46、48、66、79、82。 4. 编写程序 上面介绍完二分查找的思路和其限制条件后接下来就该讲一讲如何去实现代码了。就用该案来讲解吧下图所示序列中查找数字7看是否能找到。
1. 第一步 首先我们是要在一个有序的序列中查找某个元素的那么该序列就必须有个连续的存储空间来存放所以我们想到了用数组arr来存放。 #includestdio.h
int main()
{//存储递增的有序数列int arr[] { 1,2,3,4,5,6,7,8,9,10 };
}2. 第二步 接下来就该是找到序列的中间元素了那该怎么找我提供一个思路通过对数组元素下标的计算来找到中间元素中间元素下标mid数组最左边下标left 最右边元素下标right/ 2。 程序如下所示 #includestdio.h
int main()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列int sz sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数int mid 0;//存储中间元素的下标//左、右元素下标确定了被查找元素k的所在范围int left 0;//最左边元素的下标int right sz - 1;//最右边元素的下标int k 0;//所要查找的元素kscanf(%d, k);mid (left right) / 2;//计算中间元素的下标
}3. 第三步 然后就拿中间元素和所查找元素k进行比较这里我设置k 7发现7 5(中间元素)所以可以重新精确k的范围在中间元素之后了即最左边元素应该为中间元素后面一个left mid 1最右边元素下标right不变。 但其他的情况也不能忽略k mid时范围重新精确到了mid的左半部分就是right mid - 1left不变还有当k mid时就意味着找到所要找的那个数了就是mid下标所对应的那个数。程序如下 #includestdio.h
int main()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列int sz sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数int mid 0;//存储中间元素的下标//左、右元素下标确定了被查找元素k的所在范围int left 0;//最左边元素的下标int right sz - 1;//最右边元素的下标int k 0;//所要查找的元素kscanf(%d, k);mid (left right) / 2;//计算中间元素的下标//判断mid和看大小重新精确k所在范围if (arr[mid] k){left mid 1;}else if (arr[mid] k){right mid - 1;}else{printf(找到了\n);}
}4. 第四步 然后就是重复的去执行找中间元素下标比较mid和k大小从而更新迭代k新的范围直到mid k即找到k了为止。既然要实现重复的循环程序中自然就要用到循环体了呀那就加进去一个循环嘛。写道这里可还没算完呢我们循环条件是什么还没确定呢那循环条件如何确定呢先思考个问题若一直没找到我们所要找的元素程序会以怎样的方式结束呢 思考后我们发现在查找一个元素的时候left下标和right下标会越来越靠近甚至会指向一处这个过程中left始终在right的左边即left right。但如果一直找不到那个元素两个下标必然会相互交错即: left right这时循环结束。所以循环条件总结下来就是whileleft right。 程序最终完成如下所示
#includestdio.h
int main()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列int sz sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数int mid 0;//存储中间元素的下标//左、右元素下标确定了被查找元素k的所在范围int left 0;//最左边元素的下标int right sz - 1;//最右边元素的下标int k 0;//所要查找的元素kprintf(请输入所要查找的数);scanf(%d, k);while (left right){mid (left right) / 2;//计算中间元素的下标//判断mid和看大小重新精确k所在范围if (arr[mid] k){left mid 1;}else if (arr[mid] k){right mid - 1;}else{break;}}if (left right)printf(没有找到该数\n);else{printf(找到了\n);}
}程序执行结果如下 这份博客如果对你有帮助给博主一个免费的点赞以示鼓励欢迎各位点赞评论收藏⭐️谢谢 如果有什么疑问或不同的见解欢迎评论区留言欧。
