最简单最快的查找算法 |
您所在的位置：网站首页 › 有序数组的二分查找算法是什么 › 最简单最快的查找算法 |
最简单最快的查找算法
|
二分查找（基础）
本篇采用的计算机语言是c语言，过程中会出现c++的部分函数，函数功能都会有所提示，如果你不会c语言也没关系，代码数量不多，主要是理解算法的实现过程。 一个例子我想，大家都玩过猜数字的游戏吧：从1~100中想一个数字，玩家进行猜测，每次猜测都要给玩家一个提示：大了、小了。如果我们从1开始猜，就会出现一下场景： A：1 B：小了 A：2 B：小了 A：3 B：小了 …… 这样，我们最多可能会猜测99次！！这是个很麻烦的事，但是如果我们这样猜： A：50（１－１００的中间数） B：小了 A：７５（５０－１００的中间数） B：大了 A：６３（５０－７５的中间数） B：大了 A：５７ B：对了！ 这，就是二分查找，你已经学会这个算法的理论部分了！ 每次猜测可以排除的数字个数如下： 100个元素-（第一步）-> 50-（第二步）->25-（第三步）->13-（第四步）->7-（第五步）->4-（第六步）->2-（第七步）->1（每次使用二分查找时都可以排除一半的数字） 这样，不管我心里想的是哪个数字，你都能在七次以内猜到，因为每次猜测都可以排除很多数字！ 另一个例子如果我们要从一本包含240000个字的字典里找到一个汉字，如果采用传统的连续查找最多需要240000次！！！（我想谁都不会这么无聊）。 所以我们如果采用二分查找的方法，最多查找多少次呢？ 240000-120000-60000-30000-15000-7500-3750-1875-937-468-234-117-58-29-14-7-3-1 不用数了，我已经帮你数好了！最多需要17步就可以找到你想要的那个字了！ 由此可见，二分查找极大的减少了我们查找的次数，这放在计算机上，就会极大的优化我们程序的运行时间！ 运行时间：O(n)->O(log2n) 大家都知道log2n会随着n的增长逐渐与n拉开差距吧！ A：我们应该先知道这个数列有多少位数字，通过计算（下标为：头部下标加尾部下标/2）找到中间的那个数字（后面我们称中间数），再比较需要找的数字和中间数的大小，如果需要找的数字大于中间数，那么中间数就要更改为：（前任中间数下标+1（因为我们已经知道前任中间数不是我们要找的数，所以我们从它的下一个数开始找）+尾部下标）/2，理所当然我们的头部下标就要更改为：前任中间数的下标+1。反之，我们把尾部下标改为前任中间数下标-1。我们重复这个过程，直到找到那个数字，或者找了一遍都没有找到这个数字，此时头部和尾部下标应该重合。 可能你看了上面那段文字仍旧不够理解，那么接下来请看代码部分！ 我们通过从某一个数组内查找某一个数并返回为例子： 题目如下： 输入一个数字n表示一个数组的大小，下一行来输入n个数字（数字用空格隔开）表示数组的数据，接下来输入一个数字k，表示要查找的数字。 如果这个数字存在，则返回YES，否则返回NO。 Input 5 1 2 3 4 5 3 Output YES Input 5 1 2 3 4 5 9 Output NO #include #include//排序函数所在的函数库 using namespace std;//排序函数要用到的 int a[1000000]; int bs(int tail,int num){//bs是二分查找英文缩写，这个你可以根据自己的喜好来自定义你的函数名称。首先给函数一个尾部下标tail，表示一个数组的大小，num为你要查找的数字。 int head = 0;//我们默认数组下标从0开始 while(tail>=head){//每次查找玩如果不是想查找的那个数字，都要更新中间数，我们通过更新尾部和头部下标来更新中间数，直到头部和尾部重合都没找到这个数字，说明这个数字不存在。 int mid = head+(tail-head)/2;//当然我们可以用mid=（head+tail）/2，这是另外一种写法，防止head+tail太大而导致程序无法运行。 if(num==a[mid]){ return 1;//如果我们要找的数字找到了，就返回1； } else if(num>a[mid]){ head = mid + 1;//我们要找的数字比中间数大，所以我们也就把头部下标移动到中间数+1位置，将下次计算的中间数增加。 } else{ tail = mid - 1;//反之，我们要减小中间数。 } } return 0;//如果tail==head了，说明这个数组里没有我们要找的那个数字，返回0 } int main(){ int n; scanf("%d",&n);//输入n for(int i=0;i printf("YES\n"); } else{ printf("NO\n"); } return 0; }课下作业 输入一个数字n表示一个数组的大小，下一行来输入n个数字（数字用空格隔开）表示数组的数据，接下来输入一个数字k，表示要查找的数字。 如果这个数字存在，则输出这个数，否则输出离它最近的数字。 Input 5 1 2 3 4 5 3 Output 3 Input 5 1 2 3 4 5 9 Output 5 个人建议先跟着文章中的代码敲一遍，再去自己敲一遍，核心代码为函数bs部分，如果看到此处还不理解请在文章下方留言或私信我，我将为你一一解答。 答案： #include #include using namespace std; int a[1000000]; int bs(int tail,int num){ int head = 0; int mid; while(tail>=head){ mid = head+(tail-head)/2; if(num==a[mid]){ break; } else if(num>a[mid]){ head = mid + 1; } else{ tail = mid - 1; } } return mid; } int main(){ int n; scanf("%d",&n); for(int i=0;i |
那么问题来了 Q：我们如果想找一个有序数列中的一个数怎么办呢？【本文地址】
今日新闻 |
推荐新闻 |