所谓分治策略，就是把规模大的问题分成若干个规模小的问题来解决，最后把各自的结果再合并。
它的一般的算法设计模式如下：
Divide-and-conquer(P)
1. if |P|≤n0
2. then return(ADHOc(P))
3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)
分治策略的典型应用就是二分查找，也叫折半查找。算法的思想就是对一个有序的数组查找，搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
- public class Program
- {
- static int x = 30;
- static void Main(string[] args)
- {
- int[] array = {1,2,3,4,5,6,7,8,9,10,20,30,60,100,110};
-
- binarysearch(array, 0, array.Length - 1);
- }
-
- static int binarysearch(int[] array, int start, int end)
- {
- if (end - start <= 1)
- {
- if (array[end] == x)
- {
- Console.WriteLine("找到{0},位置{1}", x, end);
- return end;
- }
- else if (array[start] == x)
- {
- Console.WriteLine("找到{0},位置{1}", x, start);
- return start;
- }
- else
- {
- Console.WriteLine("未找到{0}", x);
- return -1;
- }
-
- }
-
- int middle = (start + end) / 2;
- Console.WriteLine("在下列有序数列中查找");
- for (int i = start; i <= end; i++)
- {
- Console.Write(array[i] + " ");
- }
- Console.WriteLine();
- Console.WriteLine("middle=({0}+{1})/2={2}", start, end, middle);
- Console.WriteLine();
-
-
-
- if (array[middle] == x)
- {
- Console.WriteLine("找到{0},位置{1}", x, middle);
- return middle;
- }
- else if (array[middle] < x)
- {
- start = middle;
- return binarysearch(array, start, end);
- }
- else
- {
- end = middle;
- return binarysearch(array, start, end);
- }
- }
-
- }
本文转自cnn23711151CTO博客，原文链接： http://blog.51cto.com/cnn237111/858556，如需转载请自行联系原作者