首页 > Python算法 > 分治算法 阅读数:32

二分查找—分治算法经典例题

我们在之前的章节中仔细地讲解了二分查找的步骤。所谓二分查找,就是通过分治思想,在一个排序好的数组中找到目标值,并且输出目标值的坐标。

二分查找与归并排序有异曲同工之处:一个是将数组对半排序,一个是在排序好的数组中对半查找目标值。通过下面的例子,我们简单地回顾一遍二分查找,在过程中理解其分治思想。示例:在数组 [0,1,2,3,4,5,6,9,10,12,11,15,16] 中查找数字 3。

如图 1 所示,在分治算法的第一步中,我们取数组的中间值 6。因为 6 比 3 大,所以我们可以放心地直接排除掉数组的后半部分,并肯定目标值只能位于数组的前半部分。
二分查找
图 1:二分查找

遵循同样的逻辑,每一步我们都将数组一分为二,将原数组变成两个相互独立的子数组,并肯定目标值在其中的一个数组里。通过对比中间值,我们直接排除一个子数组,由此节省时间。

分治思想在于,每一次我们将原问题分解成两个子问题:目标值在左数组吗?目标值在右数组吗?通过对比中间值,我们直接否定一个子问题,并递归地解决另一个子问题,直到子问题满足边界条件。