求两个已排序数组的中位数的、O(lgn)时间的算法(可以转化为不仅仅求中位数)

CLRS 9.3-7 :

给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k<=n后，它能确定出S中最接近其中位数的k个数。

算法思想：
1.找到数组a中第n/2小的数median；
2.对a中非median数进行|a[i] - median|，得到一个大小为n - 1的数组distance；
3.寻找distance中第k小的数值；
4.对distance进行一次遍历，找到小于等于k的数，从而对应得到数组a中的k个数。

上述每一步的时间复杂度都为O(n)，因而最后总的时间复杂度为O(n).

#include <iostream>
#include <time.h>
using namespace std;
//随机化分割
int randomized_partition(int* a, int p, int r);
int randomized_select(int* a, int p, int r, int i);
int main()
{
  const int LEN =12;
  int arr[LEN] = { 5, 7, 10, 3, 6, 2, 8, 9, 4, 1, 11 , 12};
  int median = randomized_select(arr, 0, LEN -1, (LEN -1)/2);
  int distance[LEN -1];
  int distance_cpy[LEN -1];

  int temp =0;
  int middle;
  for(int i =0; i < LEN; i++)
  {
    if(arr[i] != median)
      distance[temp++] = abs(arr[i] - median);
    else
      middle = i;
  }
  for(int i =0; i < LEN -1; i++)
    distance_cpy[i] = distance[i];
  int k;
  while(true)
  {
    cout<<"输入k："<<endl;
    cin>>k;
    cout<<"k邻近值为："<<endl;
    int kth_value = randomized_select(distance_cpy, 0, LEN -2, k -1);
    int* k_arr =newint[k];
    int j =0;
    //这里要注意，比如中间值为6，那么k = 3，有5,7明显符合要求，他们最近,4,8也符合要求，那么在这选择谁
    if(k%2)
    {
      bool flag =true;
      for(int i =0; i < LEN -1; i++)
      {
        if(distance[i] < kth_value)
        {
          if(i < middle)
            k_arr[j++] = median - distance[i];
          else 
            k_arr[j++] = median + distance[i];
        }
        else if(distance[i] == kth_value && flag)
        {
          if(i < middle)
            k_arr[j++] = median - distance[i];
          else 
            k_arr[j++] = median + distance[i];
          flag =false;
        }
      }
    }
    else
    {
      for(int i =0; i < LEN -1; i++)
      {
        if(distance[i] <= kth_value)
        {
          if(i < middle)
            k_arr[j++] = median - distance[i];
          else 
            k_arr[j++] = median + distance[i];
        }
      }
    }
    for(int i =0; i < k; i++)
    cout<<k_arr[i]<<"\t";
    cout<<endl;
    delete[] k_arr;
  }
}
//下标为[p, r]之间的元素
int randomized_partition(int* a, int p, int r)
{
  srand(time(NULL));
  int q = rand()%(r - p +1) + p;
  int temp = a[q];
  a[q] = a[r];
  a[r] = temp;
  int j = p;
  for(int i = p; i < r; i++)
  {
    if(a[i] < a[r])
    {
      if(i != j)
      {
        int temp2 = a[i];
        a[i] = a[j];
        a[j] = temp2;
      }
      j++;
    }
  }

  temp = a[j];
  a[j] = a[r];
  a[r] = temp;
  return j;
}
//迭代版本
int randomized_select(int* a, int p, int r, int i)
{
  int q = randomized_partition(a, p, r);
  while(p != r)
  {
    if(i == q)
      return a[q];
    else if(i < q)
    {
      r = q -1;
      q = randomized_partition(a, p, r);
    }
    else
    {
      p = q +1;
      q = randomized_partition(a, p, r);
    }
  }
  return a[p];
}