【数据结构与算法】分治法

server/2024/9/24 7:38:44/

分治法目录

一.分治法的思想
二.分治法的步骤
三.举个例子
四.具体实现
五.完整代码

一.分治法的思想

将一个大问题,拆解成为若干个小问题,而且大问题与小问题的解决方法一样.
说到这里我们可以联想到递归,没错就是用递归的思想.

分:递归解决较小的问题
治:子问题的解构建原问题的解

二.分治法的步骤

分解:将原问题分解若干个规模较小,相互独立,与原问题形式相同的子问题.
解决:若子问题规模较小而容易被解决则直接解决,否则递归的解决各个子问题.
合并:将各个子问题的解合并为原问题的解.

三.举个例子

我(你)是一个超级大帅哥,在相亲节目上被许多美女看上.
但是我想找一个身高跟我一样的美女.
于是节目组从低到高的给我排了10个妹子,但是有一堵墙,我看不到她们,只能问他她们.
节目组给我打包票里面有一位身高跟我一样,而且还是个国色天香.
但是只给我4次的询问机会,如果4次内找到就领回家,否则就答应节目组与翠花交往.
在这里插入图片描述

在这里插入图片描述
我想了一想,区区小事,何足挂齿,就答应了下来.

四.具体实现

假设这就是那10位美女的身高,而我的身高是192.
在这里插入图片描述
我心想,如果直接问未免有点太靠运气了吧,我可绝对不想与翠花交往.
那我就要保证4次内必须问到我的身高.

就在这时,我突然想到,既然是按顺序排的,那我何不从中间问起,一下就可以排除一半.
然后在剩下的一半中,我还是从中间问起,一下又可以排除一半.

哈哈哈,我来了
在这里插入图片描述

每次都是比较中间的,大就继续比较大的那部分中间,小就比较小的那部分中间.
运行结果:

最后用了三次就抱得美人归,可把翠花气坏了!

五.完整代码

#include <iostream>using namespace std;int BinarySearch(int* array, int min, int max, int num)
{if (min > max){return -1;}int mid = (min + max) / 2;if (array[mid] == num){return mid;}else if(array[mid]>num){return BinarySearch(array, min, mid - 1, num);}else{return BinarySearch(array, mid+1, max, num);}
}int main()
{int array[] = { 161,163,165,170,172,179,185,188,192,199};int length = sizeof(array) / sizeof(array[0]);cout << length << "位美女的身高分别为:" << endl;for (int i = 0; i < length; i++){cout << array[i] << " ";}cout << endl;cout <<"192身高的下标为:";int index = BinarySearch(array, 0, 9, 192);cout << index << endl;system("pause");return 0;
}