找中位数相关算法
查找第 i 大元素，除了排序外，可借助快排思想，将其划分，进而分治算法，也可堆排序
借助芯片测试，分治
http://blog.csdn.net/liu1064782986/article/details/7411720
http://blog.csdn.net/atyuwen/article/details/1817600
当有奇数个芯片两两测试，必有一个落单
1. (n-1)/2, 当分组的芯片对淘汰后保留的为奇数
1） 落单为好
奇数个芯片中好的至少比坏的多一个，无所谓加
2） 为坏
不能加
2. 为偶数
1） 落单为好
好的至少等于坏的，加
2） 落单为坏
好的至少壁坏的多两个，无所谓加
To sum up,
奇数时不加，偶数时加
分治算法，注意：
将一组数据划分后，对每个子集求解，复杂度O(logn)，而不是，求完第一个子集后，将其解并入第二个子集求解，依此类推，类似顺序法求解数组最大值，复杂度为O(n)，这根本不是分治法。
我在分析芯片测试时犯了这错，在比较两片芯片时，是先划分为 n/2组，每组独立比较，这才是分治法
1. 一个数组中位数
public static int chipTest() { int i = 0, j = 0; int[] a = copyArray(elements); int[] tmp = new int[a.length]; while(a.length > 3) { j = 0; for(i = 0; i+1 < a.length; i=i+2) { if(a[i]== a[i+1]) { tmp[j] = a[i]; j++; } } if(j%2 == 0 && i== a.length-1) { tmp[j] = a[i]; } a = copyArray(tmp); } if(a.length == 3) { if(a[0]==a[1]) { return a[0]; } else { return a[2]; } } else if(a.length == 2) { if(a[0] == a[1]) { return a[0]; } else { return -1; } } else { return a[0]; }}float GetMedian(int _ia, int _ja, int _ib, int _jb) {if((_ja-_ia)%2==0 && g_a[(_ia+_ja)/2]==g_b[(_ib+_jb)/2]) {return g_a[(_ia+_ja)/2];}if((_ja-_ia)%2==1 && g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1]==g_b[(_ib+_jb)/2]+g_b[(_ib+_jb)/2+1]) {return (float)(g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1])/2;}if(_ja-_ia == 1) {return (float)(max(g_a[_ia], g_b[_ib])+min(g_b[_ja], g_b[_jb]))/2;}if((_ja-_ia)%2==0) {if(g_a[(_ia+_ja)/2] < g_b[(_ib+_jb)/2]) {return GetMedian((_ia+_ja)/2, _ja, _ib, (_ib+_jb)/2);} else {return GetMedian(_ia, (_ia+_ja)/2, (_ib+_jb)/2, _jb);}} else {if(g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1] < g_b[(_ib+_jb)/2]+g_b[(_ib+_jb)/2+1]) {return GetMedian((_ia+_ja)/2+1, _ja, _ib, (_ib+_jb)/2);} else {return GetMedian(_ia, (_ia+_ja)/2, (_ib+_jb)/2+1, _jb);}}}return (float)(max(g_a[_ia], g_b[_ib])+min(g_b[_ja], g_b[_jb]))/2;