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

分治法目录

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

一.分治法的思想

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

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

二.分治法的步骤

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

三.举个例子

我(你)是一个超级大帅哥,在相亲节目上被许多美女看上.
但是我想找一个身高跟我一样的美女.
于是节目组从低到高的给我排了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;
}

2024年8月16日20:51:18