CareerCup

It's basically find kth element of two sorted arrays when merged. In you case, find the mid point i.e. (m+n)/2 th element. (m,n being sizes of arrays). Worst case complexity would be just merging until we get (m+n)/2 elements i.e. O((m+n)/2). Am working on a better algo. has a complexity
O(m/2 + log2m).

Google for "dichotomic search". That is the most efficient algorithm.

Check
geeksforgeeks.org/?p=2105

for O(log n) time algorithm.

Please check my code:

#include<stdio.h>

int findKthsmallest(int a[],int m,int b[],int n,int k)
{
	int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
	while(1)
	{
		ti = (int)((double)m/(m+n) * (k-1));
		tj = (k-1)-ti;
		i = I+ti;
		j= J+tj;
		//printf(" i=%d j=%d\n",i,j);
		if(j>0 && j<N && i<M && a[i]>b[j-1] && a[i]<b[j])
			return a[i];
		if(i>0 && i<M && j<N && b[j]>a[i-1] && b[j]<a[i])
			return b[j];
		if(j==0 && i<M && a[i]<b[j])
			return a[i];
		if(i==0 && j<N && b[j]<a[i])
			return b[j];
		if(j==N && a[i]>b[j-1])
			return a[i];
		if(i==M && b[j]>a[i-1])
			return b[j];
		if(i<M && j<N)
		{
			if(a[i]<b[j])
			{
				k=k-ti-1;
				m=m-ti-1;
				I=i+1;
			}
			else
			{
				k=k-tj-1;
				n=n-tj-1;
				J=j+1;
			}
		}
		else if(i>=M)
		{
			k=k-tj-1;
			n=n-tj-1;
			J=j+1;
		}
		else
		{
			k=k-ti-1;
			m=m-ti-1;
			I=i+1;
		}
	}
}

int main()
{
	int a[]={1,2,3};
	int b[]={4};
	int m=3,n=1,k=3;
	printf("%d",findKthsmallest(a,m,b,n,k));
	return 0;
}