看到这个标题无论你是处于怎样的心理进来看了,我觉得都是值得的。因为这个问题太简单,任何一个开始接触“真正”算法基本都是从二分查找开始的。至于二分查找都不知道是什么的可以先去找别的资料看下,再来看这篇文章。既然很简单,那么我们开始一起写一个吧,要求是对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吧,整个程序就写好了,如下:
-
int
bSearch(
int
begin,
int
end,
int
e)
-
{
-
int
mid, left = begin, right = end;
-
while
(left < right)
-
{
-
mid = (left + right) >> 1;
-
if
(num[mid] > e) right = mid;
-
else
left = mid;
-
}
-
return
mid;
-
}
补充好整个程序后运行吧!查找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
-
int
bSearch(
int
begin,
int
end,
int
e)
-
{
-
int
mid, left = begin, right = end;
-
while
(left <= right)
-
{
-
mid = (left + right) >> 1;
-
if
(num[mid] >= e) right = mid - 1;
-
else
left = mid + 1;
-
}
-
return
left;
-
}
对于YES_RIGHT或者NO_LEFT
-
int
bSearch(
int
begin,
int
end,
int
e)
-
{
-
int
mid, left = begin, right = end;
-
while
(left <= right)
-
{
-
mid = (left + right) >> 1;
-
if
(num[mid] > e) right = mid - 1;
-
else
left = mid + 1;
-
}
-
return
right;
-
}
不做过多说明,单步调试自然会发现执行过程,要说明的是,两个程序都用了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
java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分查找 java 二分查找java 二分...
* 不适合大规模数据:二分查找的时间复杂度虽然低,但是当数组规模很大时,二分查找的效率会下降。 四、Java 二分查找的应用 Java 二分查找的应用非常广泛,例如: * 数据库查询:在数据库中,二分查找可以用于...
二分查找,也被称为折半查找,是一种在有序数组中高效搜索特定元素的算法。它以其高效率和在适当数据结构中的广泛适用性而闻名。本文将深入探讨两种不同的二分查找实现:健忘版和识别版,并分析它们的效率差异。 ...
然而,如果数据未排序或经常需要插入和删除元素,二分查找可能不是最佳选择,因为这些操作会破坏已排序的顺序。 ### 5. 扩展讨论 - **变种与优化**:二分查找可以进行一些变种,例如对链表的二分查找,或者在有...
需要注意的是,二分查找的前提是数据必须是有序的,因此在实际应用中,我们通常会在对数据排序后使用二分查找。例如,在大型数据集的查找、插入和删除操作中,结合排序和二分查找可以极大地提高效率。 总的来说,二...
"折半查找(二分查找)" 折半查找(二分查找)是一种高效的查找算法,对于顺序存储的有序表,可以快速地找到指定的关键字记录。该算法的基本思想是,每次比较给定值 K 与中间位置记录的关键字值,并根据比较结果...
**二分查找(Binary Search)**是一种在有序数组中寻找特定元素的搜索算法。它的基本思想是通过比较中间元素与目标值,不断缩小搜索范围,直到找到目标元素或者确定其不存在。二分查找的时间复杂度为O(log n),在大...
二分查找是一种在有序数组中查找特定元素位置的算法,它利用数组元素排序的特性,通过比较数组中间元素与目标值的大小,将查找区间缩半来加快查找速度。该算法适用于有序集合,能够将时间复杂度从线性查找的O(n)降低...
### C++ 二分查找法详解 在计算机科学领域,数据结构与算法是核心课程之一,其中二分查找法(Binary Search)是一种高效的查找技术,尤其适用于有序数组或列表的搜索场景。本文将深入探讨C++中实现二分查找法的具体...
在这个"flash as3 二分查找动画演示"项目中,我们看到的是一个用Flash AS3实现的二分查找算法的可视化教程。 二分查找(Binary Search)是计算机科学中一种高效的数据检索方法,适用于已排序的数组或列表。它的基本...
在给定的代码中,二分查找算法函数sq_Dichotomy_Search0实现了有序数组的二分查找。它的参数包括被查找数组、数组元素个数和被查找的关键值。函数返回的值是目标元素在数组中的下标,如果没有找到则返回-1。 插值...
在实际的VC++项目中,你可以将二分查找算法应用到各种场景,如在大型数据库中查找特定记录,或者在处理大量数字时快速定位特定值。同时,了解并掌握二分查找也是理解和设计其他高级算法,如平衡二叉搜索树、跳表等的...
二分查找算法是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且...
二分查找算法是一种高效的数据搜索方法,主要应用于已排序的序列。它的基本思想是通过不断地将待搜索区域减半来快速定位目标值。这个过程基于分治策略,将大问题分解为更小的子问题来解决。在二分查找算法中,每次...
二分查找ppt