两个数组中求第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]