2개의 정렬된 배열을 합쳤을 때의 중간값 구하기

     +---------------------------------------+
     | Array A                               |
     +---------------------------------------+
        +---------+    |     +--+  
        |         |    |     |  |    Array B
        +---------+    |     +--+
                       |
                   <---| 이동

  +----------++---------------------+
  | Array B  || Array A             |
  +----------++---------------------+

#include <stdio.h>
#include <vector>

using namespace std;

int find_middle(int *a, int size_a, int *b, int size_b);
void show_array(int *a, int size_a, int *b, int size_b);
int lsearch(int *sp, int size_sp, int search_n);

int main(int argc, char **argv)
{
		int a[] = {5, 8, 10, 14, 19, 20, 25, 30, 33, 35, 39};
		int b[] = {5, 8, 25};

		show_array(a, sizeof(a)/4, b, sizeof(b)/4);
		find_middle(a, sizeof(a)/4, b, sizeof(b)/4);
		return 0;
}

int find_middle(int *a, int size_a, int *b, int size_b)
{
		int *largep;
		int *smallp;
		int smallsize;
		int largesize;
		int idx;
		if (size_a > size_b)
		{
				largep = a;
				smallp = b;
				idx = size_a/2;
				smallsize = size_b;
				largesize = size_a;
		}
		else
		{
				largep = b;
				smallp = a;
				smallsize = size_a;
				largesize = size_b;
				idx = size_b/2;
		}

		// large array의 중간값보다 작은 값의 범위에 대해서
		int li = 0;
		int si = 0;
		int left_size=0;
		int leftsame=0;
		int same=0;
		printf("pivot : %d %d\n", idx, largep[idx]);

		printf("Large %d , Small %d\n", largesize, smallsize);
		while(1)
		{
				if (li == largesize-1 && si == smallsize-1) break;

				printf("%d %d\n", largep[li], smallp[si]);
				if (largep[li] == smallp[si])
				{
					same++;
					if (li < idx) leftsame++;
					if (li < largesize-1)
						li++;
					if (si < smallsize-1)
						si++;
				}
				else if(largep[li] > smallp[si])
				{
					if (si < smallsize-1)
						si++;
					else
						li++;
				}
				else
				{
					if (li < largesize-1)
						li++;
				}
				sleep(1);
		}

		printf("Small Insert Size %d %d\n", leftsame, same);

		// large array의 중간값보다 큰것들 비교
		int right_size = 0;
		same = 0;
		int small_center = si;
		printf("small Center : %d\n", si);
		printf("Center %d\n", largep[li]);


		right_size -= same;
		printf("Large insert %d\n", right_size);

		int offset = (right_size - left_size)/2;

		// 대략 idx를 기준으로 앞으로 2만큼 이동시킨게 중간값임을 알 수 있다.
		// 이제 실제 idx를 이동시키면서 원하는 값을 찾아보자.

		printf("Offset is %d\n", offset);
		int big_center = size_a/2;
		int value;
		if (offset > 0)
		{
			while(offset)
			{
				if (largep[big_center] > smallp[small_center])
				{
					big_center --;
					offset --;
					value = largep[big_center];
				}
				else if (largep[big_center] < smallp[small_center])
				{
					small_center --;
					offset --;
					value = smallp[small_center];
				}
				else
				{
					small_center --;
					big_center --;
					value = smallp[small_center];
				}
			}
			printf("[1] middle Value : %d \n", value);
		}
		else
		{
			value = largep[big_center];
			while(offset)
			{
				if (largep[big_center] < smallp[small_center])
				{
					big_center ++;
					offset ++;
					value = largep[big_center];
				}
				else if (largep[big_center] > smallp[small_center])
				{
					small_center ++;
					offset ++;
					value = smallp[small_center];
				}
				else
				{
					small_center ++;
					big_center ++;
					value = smallp[small_center];
				}
			}
			printf("[2] middle Value : %d\n", value);
		}

		return 0;
}

// 경우에 따라서 binary 검색으로 할 수 있다.
int lsearch(int *sp, int size_sp, int search_n)
{
		int i = 0;
		while(i < size_sp)
		{
				if ( *(sp+i) > search_n)
						return i;
				i++;
		}
		return 0;
}

void show_array(int *a, int size_a, int *b, int size_b)
{
	int i = 0;
	printf("[ ");
	for(i = 0; i < size_a; i++)
	{
		printf("%d ",a[i]);
	}
	printf("]\n");

	printf("[ ");
	for(i = 0; i < size_b; i++)
	{
		printf("%d ",b[i]);
	}
	printf("]\n");
}