以图明志

计算机算法

[专题] 漫谈递归:二分查找算法的递归实现

用递归写一个二分查找
还有一个典型的递归例子是对已排序数组的二分查找算法。现在有一个已经排序好的数组,要在这个数组中查找一个元素,以确定它是否在这个数组中,很一般的想法是顺序检查每个元素,看它是否与待查找元素相同。这个方法很容易想到,但它的效率不能让人满意,它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

计算机算法

只有10%的程序员可以把二分查找写正确

直到1962年才有没bug的二分查找
二分查找可以解决(预排序数组的查找)问题:只要数组中包含T(即要查找的值),那么通过不断缩小包含T的范围,最终就可以找到它。一开始,范围覆盖整个数组。将数组的中间项与T进行比较,可以排除一半元素,范围缩小一半。就这样反复比较,反复缩小范围,最终就会在数组中找到T,或者确定原以为T所在的范围实际为空。
1 / 1 首页 < Prev 1 Next > 尾页 页码: