1.算法知识点
??分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
2.算法题目描述
2.1 二分搜索
??某大型娱乐节目在玩猜数字游戏：主持人在女嘉宾的手心写一个10以内的整数，让女嘉宾的老公猜主持人写的数字是几，每猜一次，女嘉宾只能提示大了或者小了，并且只有三次机会。
??随机写一个1~n的整数，有没有办法以最快的速度猜出来呢？
2.1.1问题分析
从问题描述看，如果是n个数，最坏的情况是猜n次才能成功。我们注意到这些数字是有序的，可以使用二分搜索策略，如果猜的数x比中间元素大，则缩小范围1~n为n*1/2 ~ n，这样一下子减小了一半的数据量，太爽了！！！
2.1.2算法设计
int BinarySearch(int s[],int n ,int x)
{
int left = 0, right = n - 1;//left为上界，right为下界
while (left <= right) //当上界小于下界，循环一直进行
{
int middle = (left + right) / 2;//middle为查找范围中间元素的下标
if (s[middle] == x) //找到返回其下标
return middle;
else if (s[middle < x]) //找不到
{
right = middle - 1; //缩小范围
}
else
{
left = middle + 1;
}
}
return -1;
}
2.1.3详细图解
2.2归并排序
??数列中如果只有一个数，那么数列本身就是有许多；数列中如果只有两个数，那么数列结果一次比较就可以完成排序。也就是说，数列中的数越少，排序越容易。对于一个由大量数字组成的数列，将很难快速地完成排序，该怎么办呢？
2.2.1问题分析
??首先将待排序元素分解为两个规模大致相等的子序列，如果仍不易解决，则继续分解子序列，直到子序列只有一个元素。由于只有一个元素的序列本身有序，因此可对这些有序的子序列进行合并，最终得到完整的有序序列。
2.2.2详细图解
我们取部分进行分析。
首先分解是简单的，将一个序列从中间分开很好理解吧。
但是合并就有一点难度了，
合并的基本思想：
??设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
??重复步骤，直到某一指针超出序列尾
??将另一序列剩下的所有元素直接复制到合并序列尾
最后就形成3、4、6、10的序列，再和右边形成的数列合并…
2.2.3算法设计
void Merge(int a[], int left, int middle, int right)
{
int* b = new int[right - left + 1];//辅助数组b
int i = left;
int j = middle + 1;
int k = 0;
while (i <= middle && j <= right)
{
if (a[i] <= a[j]) //将较小的元素放入辅助数组b中
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i <= middle) //前半部分有剩余，将剩余的放入数组b中
b[k++] = a[i++];
while (j <= right) //后半部分有剩余，将剩余的放入数组b中
b[k++] = a[j++];
for (i = left, k = 0; i <= right; ++i)
{
a[i] = b[k++]; //将有序数组放回a中
}
delete[] b;
}
void MergeSort(int a[], int left,int right)
{
if (left < right)
{
int middle = (left + right) / 2;
MergeSort(a, left, middle);//前半部分合并
MergeSort(a, middle+1, right);//后半部分合并
Merge(a, left, middle,right);//前后合并
}
}
