Տրված են երկու n չափանի սորտավորված զանգվածներ։ Գտնել դրանց միավորումից ստացված զանգվածի մեջտեղի տարրը։ Ալգորիթմի բարդությունը O(logn):

Median problem

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

int get_median(int* a, int s)
{
	if(s % 2 == 0)
	{
		return (a[s/2] + a[s/2 - 1]) / 2;
	}
	else
	{
		return a[s/2];
	}
}

int median(int* a1, int* a2, int l)
{
	int m1 = get_median(a1, l);
	int m2 = get_median(a2, l);

	if(l <= 0)
	{
		return -1;
	}
	if(l == 1)
	{
		return (a1[0] + a2[0])/2;
	}
	if(l == 2)
	{
		return (std::max(a1[0], a2[0]) + std::min(a1[1], a2[1]))/2;
	}
	if(m1 == m2)
	{
		return m1;
	}
	if(m1 > m2)
	{
		if(l % 2 == 0)
		{
			return median(a1, a2 + l/2 + 1, l - l/2 + 1 );
		}
		else
		{
			return median(a1, a2 + l/2, l - l/2);
		}
	}
	else
	{
		if(l % 2 == 0)
		{
			return median(a1 + l - l/2 + 1, a2, l - l/2 + 1 );
		}
		else
		{
			return median(a1 + l - l/2, a2, l - l/2);
		}
	}
}

int main()
{
	int a1[] = {1, 3, 5, 8, 9};
	int a2[] = {2, 4, 7, 10, 13};
	int l = sizeof(a1)/sizeof(a1[0]);
	int m = median(a1, a2, l);
	std::cout << " median " << m << std::endl;
	return 0;
}