分治法——见名思义,即分而治之,从而得到我们想要的最终结果。分治法的思想是将一个规模为 N 的问题分解为 k 个较小的子问题,这些子问题遵循的处理方式就是互相独立且与原问题相同。 两部分组成: 分(divide):递归解决较小的问题 治(conquer):然后从子问题的解构建原问题的解 三个步骤: 1、分解(Divide):将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题; 2、解决(Conquer):若子问题规模较小而容易被解决则直接解决,否则递归地解各个子问题; 3、合并(Combine):将各个子问题的解合并为原问题的解。 例题: 一个装有 16 枚硬币的袋子,16 枚硬币中有一个是伪造的,伪造的硬币和普通硬币从表面上看不出有任何差别,但是那个伪造的硬币比真的硬币要轻。现有给你一台天平,请你在尽可能最短的时间内找出那枚伪造的硬币。 解答:我们先将 16 枚硬币分为左右两个部分,各为 8 个硬币,分别称重,必然会有一半轻一半重,而我们要的就是轻的那组,重的舍去。接下来我们继续对轻的进行五五分,直至每组剩下一枚或者两枚硬币,这时我们的问题自然就解决了。
#include <iostream> #include <Windows.h> using namespace std; //递归实现二分查找 //arr:有序数组地址 //minSub:查找范围的最小下标 //maxSub:查找范围的最大下标 //num:待查找数字 int BinarySearch(int* arr, int minSub, int maxSub, int num) { if (minSub > maxSub) { return -1; //找不到num时,直接返回-1 } int mid = (minSub + maxSub) / 2; if (num == arr[mid]) { return mid;//找到num时直接返回下标 } else if (num < arr[mid]) { return BinarySearch(arr, minSub, mid-1, num); } else { return BinarySearch(arr, mid + 1, maxSub, num); } } int main() { int arr[10] = {5,7,11,15,19,21,25,26,61,99}; int index = BinarySearch(arr, 0, 9, 26); cout << "index:" << index << endl; system("pause"); return 0; }