第二章实践作业

分治法找第 k 小的数：基础理解与思考
一、用分治法找第 k 小的数
找第 k 小的数，用分治法来解决其实思路还挺直观的。大概可以分成这几步：
先选一个 “基准数”，随便从数组里挑一个就行，比如选第一个或者最后一个
把数组分成两部分：比基准数小的放左边，比基准数大的放右边（和快排的分区很像）
看看基准数在数组里的位置：
如果它的位置正好是 k-1（数组从 0 开始数），那它就是第 k 小的数
如果位置比 k-1 小，说明第 k 小的数在右边，就去右边找
如果位置比 k-1 大，说明第 k 小的数在左边，就去左边找
重复上面的步骤，直到找到目标
伪代码
function 找第k小(数组, 左边界, 右边界, k):
if 左边界 == 右边界:
return 数组[左边界]
基准位置 = 分区(数组, 左边界, 右边界) # 分区后返回基准数的位置
if 基准位置 == k-1:
return 数组[基准位置]
elif 基准位置 > k-1:
return 找第k小(数组, 左边界, 基准位置-1, k)
else:
return 找第k小(数组, 基准位置+1, 右边界, k)
二、时间复杂度分析
这个算法的时间复杂度和选的基准数关系很大：
最好情况：每次都能选到中间大小的数当基准，这样每次都能把数组分成差不多两半。这种情况下时间复杂度是 O (n)，因为每次处理的数组长度是n，n/2、n/4。。加起来差不多是2n，所以是线性时间。
最坏情况：运气不太好，每次选的基准都是最大或最小的数。比如要找最小的数，却每次都选最大的当基准，这样每次只能排除一个元素，时间复杂度就变成了 O (n²)，和最差情况的快排一样。
不过实际用的时候，我们可以随机选基准数，这样出现最坏情况的概率就很低啦。
三、对分治法的体会
学了分治法之后，最大的感受就是 “化繁为简”。它的核心思路就是把一个大问题拆成几个小问题，小问题解决了，大问题也就解决了。
就像找第 k 小的数，本来要在整个数组里找，用分治法一拆，每次只需要处理一半的元素，问题规模越来越小，解决起来就轻松多了。
分治法给我的另一个启发是 “递归思维”，很多分治算法都用递归来实现，因为子问题和原问题的结构是相似的。不过拆的时候也要注意，子问题不能太复杂，而且最好能独立解决，不然反而会更麻烦。
总的来说，分治法就像我们解决难题时，把大任务分解成小步骤一样，是一种很实用的解题思路