两个数组中求第k小数

真言

幸福的人生是不存在的，什么叫幸福？不完美的完美就是幸福。

引言

陈利人先生的题目很有思考性，很喜欢。

题目

给两个同样长度排好序的数组，找出第k个最小的数。

思路

思路很清晰，借鉴与折半查找，不断减小查找范围。

举个例子吧，两个数组（a and b）如下（一共16个数），看看我们是怎么减小搜索范围的，我们找出第九小的数

第九小的数肯定在两个数组的前九个里，但是每个数组就八个数，所以没有减小范围。然后找出数组a的中间数，如下

再在数组b里折半查找这个数，如下

发现不存在，则返回最靠近查找数的数，如上。然后这时候我们发现这两个数以及其前面的数一共是5个，所以第六小数肯定不在刚才那个范围里，则缩小范围

缩小后，得到的范围如下，则查找第（6-5）小数，即第一小数，这时候就特简单了。

实验

代码

test.cpp

#include
using namespace std;

// define size for array
const int size = 20;

// function declare to the problem
int Super_bisearch(int * A,const int Asize,int * B,const int Bsize,const int k);
// function declare to binary search
int Bisearch(int *d,int length,int key );

// function main
int main()
{

	int * A = new int[size];
	int * B = new int[size];
	for(int i = 0;i<> (Asize+Bsize))
	{
		cout<<"exception of input super_bisearch"< 2 &&(sa ( ca + cb - sa - sb) )
		{
			number = number - ( ca + cb - sa - sb );
			sa = ca;
			sb = cb;	
			if( ( ca + cb - sa - sb ) == 0) break;
		}
		else if( ( ca + cb - sa - sb) == number )
		{
			return A[ca]>B[cb]?A[ca]:B[cb];
		}
		else if( number < ( ca + cb - sa - sb) )
		{
			ba = ca;
			bb = cb;
		}
	}
	int * d = new int[ba-sa+1+bb-sb+1];
	int i = sa,j = sb,bit = 0;
	while(i <= ba && j <= bb)
	{
		if(A[i] d[c] )
			{
				s = c;
				if( e-s == 1 && d[s]