`
mixer_b
  • 浏览: 115081 次
社区版块
存档分类
最新评论

你真的会二分查找吗?

阅读更多

  看到这个标题无论你是处于怎样的心理进来看了,我觉得都是值得的。因为这个问题太简单,任何一个开始接触“真正”算法基本都是从二分查找开始的。至于二分查找都不知道是什么的可以先去找别的资料看下,再来看这篇文章。既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不减序列在区间[0,7)进行查找,当然我们得首先保证要查找的数e满足:num[0] <= e <= num[0],这个是很容易做到的,为了简化又不失去代表性,e选取2、3、4这三个数。我们就一起开始写吧:

       首先,很容易的写下 int bSearch(int begin, int end, int e)

       然后,很自然的定义 int mid, left = begin, right = end;

       接下来怎么写呢?while(left < right)?while(left <= right)?while(mid == left)?while(mid == right)?………………真正一个写程序人会想纠结好一会儿,我们就选一个吧while(left < right)

       下面,也很自然,min = (left + right) >> 1; 用位云算能节省一些时间呢!

        现在呢?又是纠结的时候了吧?if(num[mid] > e)?if(num[mid] >= e)?我们也随便选一个吧,if(num[mid] > e)

        其实,下面你会不断纠结……right = mid;这是正常人的写法,但是有时候也会看到别人写成right = mid - 1;我们也考虑下吧,但是现在我们就直接写right = mid;

        有if了当然也会有else,然后理所当然 left = mid;同样记住还有一个选择left = mid + 1;


不错,整个while循环搞定了,最后就是返回了,写下return的时候是不是又纠结了?left?right?mid?算了,就写mid吧,整个程序就写好了,如下:

[cpp]   view plain copy print ?
  1. int  bSearch( int  begin,  int  end,  int  e)  
  2. {  
  3.     int  mid, left = begin, right = end;  
  4.     while (left < right)  
  5.     {  
  6.         mid = (left + right) >> 1;  
  7.         if (num[mid] > e) right = mid;  
  8.         else  left = mid;  
  9.     }  
  10.     return  mid;  
  11. }  

 

        补充好整个程序后运行吧!查找2、3、4的时候都没有结果出现!!比如查4的时候,单步调试会发现当mid=4,left=4,right=5,接下来就一直在while里循环,保持不变!问题到底在哪?问题在很多地方,因为我们上面的遇到很多选择,没有结果是多个选择作用的共同的结果,通过修修补补也可以得到想要的结果,其它例子就不举了,直接说说本文章讨论的关键吧。我总结的二分无非就4种情况:YES_LEFT、YES_RIGHT、NO_LEFT、NO_RIGHT,分别代表:能找到且返回最左边的数的位置(如查找4的时候返回位置3)、能找到且返回最右边的数的位置(如查找4的时候返回位置4)、不能找到且返回左边与其接近的数的位置(如查找3的时候返回位置2)、不能找到且返回右边与其接近的数的位置(如查找3的时候返回位置3)。下面是我总结调试的代码:


对于YES_LEFT或者NO_RIGHT

[cpp]   view plain copy print ?
  1. int  bSearch( int  begin,  int  end,  int  e)  
  2. {  
  3.     int  mid, left = begin, right = end;  
  4.     while (left <= right)  
  5.     {  
  6.         mid = (left + right) >> 1;  
  7.         if (num[mid] >= e) right = mid - 1;  
  8.         else  left = mid + 1;  
  9.     }  
  10.     return  left;  
  11. }  

对于YES_RIGHT或者NO_LEFT

[cpp]   view plain copy print ?
  1. int  bSearch( int  begin,  int  end,  int  e)  
  2. {  
  3.     int  mid, left = begin, right = end;  
  4.     while (left <= right)  
  5.     {  
  6.         mid = (left + right) >> 1;  
  7.         if (num[mid] > e) right = mid - 1;  
  8.         else  left = mid + 1;  
  9.     }  
  10.     return  right;  
  11. }  

 

       不做过多说明,单步调试自然会发现执行过程,要说明的是,两个程序都用了right = mid - 1; left = mid +1;用这个的前提是终止条件要是left <= right。要注意的是,有的二分查找不是只需要四种情况中的一种,而是组合使用,比如查找一个数,如果找到则×××不然则×××,如果是YES_LEFT || NO_RIGHT组合或者YES_RIGHT || NO_LEFT组合就直接用上面代码即可,否则就要综合用了,加一些判断等说明,因为用的时候不多,就不给出代码了,自己如果遇到可以试着写写,当成模板,以后直接用~

       现在,是不是觉得二分查找很容易呢?如果总结过的话……

分享到:
评论

相关推荐

    二分查找_测试

    在实际编程中,通常会使用循环结构实现二分查找。例如,以下是一个简单的C++实现: ```cpp int binarySearch(int arr[], int left, int right, int target) { while (left ) { int mid = left + (right - left) /...

    二分查找算法

    二分查找算法 二分查找算法是一种高效的查找算法,适用于已经排好序的数组或链表中查找特定的元素。该算法的时间复杂度为O(log n),远远优于顺序查找算法的O(n)。 二分查找算法的基本思想是将数组或链表分成两个...

    二分查找算法PPT课件

    二分查找算法,二分查找算法课件,二分查找算法PPT

    java 二分查找 java 二分查找

    java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分...

    java二分查找实现

    * 不适合大规模数据:二分查找的时间复杂度虽然低,但是当数组规模很大时,二分查找的效率会下降。 四、Java 二分查找的应用 Java 二分查找的应用非常广泛,例如: * 数据库查询:在数据库中,二分查找可以用于...

    二分查找办法

    二分查找,也被称为折半查找,是一种在有序数组中高效搜索特定元素的算法。它以其高效率和在适当数据结构中的广泛适用性而闻名。本文将深入探讨两种不同的二分查找实现:健忘版和识别版,并分析它们的效率差异。 ...

    VB 二分查找

    然而,如果数据未排序或经常需要插入和删除元素,二分查找可能不是最佳选择,因为这些操作会破坏已排序的顺序。 ### 5. 扩展讨论 - **变种与优化**:二分查找可以进行一些变种,例如对链表的二分查找,或者在有...

    二分查找解题

    需要注意的是,二分查找的前提是数据必须是有序的,因此在实际应用中,我们通常会在对数据排序后使用二分查找。例如,在大型数据集的查找、插入和删除操作中,结合排序和二分查找可以极大地提高效率。 总的来说,二...

    折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)

    "折半查找(二分查找)" 折半查找(二分查找)是一种高效的查找算法,对于顺序存储的有序表,可以快速地找到指定的关键字记录。该算法的基本思想是,每次比较给定值 K 与中间位置记录的关键字值,并根据比较结果...

    深入理解二分查找(一、二分查找及其变体)

    **二分查找(Binary Search)**是一种在有序数组中寻找特定元素的搜索算法。它的基本思想是通过比较中间元素与目标值,不断缩小搜索范围,直到找到目标元素或者确定其不存在。二分查找的时间复杂度为O(log n),在大...

    二分查找最简单教程

    二分查找是一种在有序数组中查找特定元素位置的算法,它利用数组元素排序的特性,通过比较数组中间元素与目标值的大小,将查找区间缩半来加快查找速度。该算法适用于有序集合,能够将时间复杂度从线性查找的O(n)降低...

    C++ 二分查找法

    ### C++ 二分查找法详解 在计算机科学领域,数据结构与算法是核心课程之一,其中二分查找法(Binary Search)是一种高效的查找技术,尤其适用于有序数组或列表的搜索场景。本文将深入探讨C++中实现二分查找法的具体...

    flash as3 二分查找动画演示

    在这个"flash as3 二分查找动画演示"项目中,我们看到的是一个用Flash AS3实现的二分查找算法的可视化教程。 二分查找(Binary Search)是计算机科学中一种高效的数据检索方法,适用于已排序的数组或列表。它的基本...

    查找算法集(顺序查找、二分查找、插值查找、动态查找)

    在给定的代码中,二分查找算法函数sq_Dichotomy_Search0实现了有序数组的二分查找。它的参数包括被查找数组、数组元素个数和被查找的关键值。函数返回的值是目标元素在数组中的下标,如果没有找到则返回-1。 插值...

    二分查找算法 VC++

    在实际的VC++项目中,你可以将二分查找算法应用到各种场景,如在大型数据库中查找特定记录,或者在处理大量数字时快速定位特定值。同时,了解并掌握二分查找也是理解和设计其他高级算法,如平衡二叉搜索树、跳表等的...

    二分查找算法流程图流程图举例

    二分查找算法是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且...

    算法分析与设计-实验二 二分查找实验报告.docx

    二分查找算法是一种高效的数据搜索方法,主要应用于已排序的序列。它的基本思想是通过不断地将待搜索区域减半来快速定位目标值。这个过程基于分治策略,将大问题分解为更小的子问题来解决。在二分查找算法中,每次...

    二分查找ppt

    二分查找ppt

Global site tag (gtag.js) - Google Analytics