fork download 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. int ssearch(int *a,int l,int h,int k)
  5. {
  6. 	if(l + k -1 > h)
  7. 		return -1;
  8. 	else
  9. 		return a[l+k-1];	
  10. }
  11.  
  12. int kthlargest(int *a,int *b,int la,int ra,int lb,int rb,int k)
  13. {
  14. 	//get optimum mida and midb	
  15. 	int mida = la + k/2 - 1,midb = lb + k/2 - 1 + k%2;
  16.  
  17. 	if(midb>rb)
  18. 	{
  19. 		mida += midb-rb;
  20. 		midb = rb;
  21. 	}
  22. 	else if(mida>ra)
  23. 	{
  24. 		midb += mida-ra;
  25. 		mida =  ra;
  26. 	}
  27.  
  28. 	//check extremes in case one array expires
  29.  
  30. 	if(mida<la && midb<lb)
  31. 		return -1;
  32. 	if(mida>ra || mida<la || la>ra)
  33. 	{
  34. 		if(la>ra)
  35. 			return ssearch(b,lb,rb,k);
  36. 		else
  37. 			return ssearch(b,lb,rb,k -(ra-la+1));
  38. 	}
  39. 	if(midb>rb || midb<lb || lb>rb)
  40. 	{
  41. 		if(lb>rb)
  42. 			return ssearch(a,la,ra,k);
  43. 		else
  44. 			return ssearch(a,la,ra,k -(rb-lb+1));		
  45. 	}	
  46.  
  47. 	//logic
  48. 	//both mid at last positions		
  49. 		if(midb==rb)
  50. 			if(mida==ra)
  51. 				return a[mida]>=b[midb] ? a[mida] : b[midb];
  52. 	//either way
  53. 		if(b[midb]>=a[mida])
  54. 			if(mida==ra || a[mida+1]>=b[midb])
  55. 				return b[midb];
  56. 			else
  57. 				return kthlargest(a,b,mida+1,ra,lb,midb-1,k-mida-1+la);
  58.  
  59. 		else
  60. 			if (midb==rb || a[mida]<=b[midb+1])
  61. 				return a[mida];
  62. 			else
  63. 				return kthlargest(a,b,la,mida-1,midb+1,rb,k-midb-1+lb);
  64. }
  65.  
  66.  
  67. int main()
  68. {
  69. 	int a[]={4,8,12,18,25,33,56};
  70. 	int b[]={1,2,3,6,17,18,25,26,32,89};
  71. 	int k,i;
  72.  
  73. 	for(i=0;i<sizeof(a)/sizeof(int);i++)
  74. 		printf(" %d ",a[i]);
  75. 	printf("\n");
  76.  
  77. 	for(i=0;i<sizeof(b)/sizeof(int);i++)
  78. 		printf(" %d ",b[i]);
  79. 	printf("\n");
  80.  
  81. 	printf("enter k\n");
  82. 	scanf("%d",&k);
  83. 	if(k==1)
  84. 		printf("kth smallest is %d\n",a[0]>b[0]?b[0]:a[0]);
  85. 	else
  86. 		printf("k th smallest element is %d\n",kthlargest(a,b,0,sizeof(a)/sizeof(int)-1,0,sizeof(b)/sizeof(int)-1,k));
  87. 	return 0;
  88. }
  89.  
  90.  
stdin 
15
compilation info 
prog.c: In function ‘main’:
prog.c:82: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
stdout 
 4  8  12  18  25  33  56 
 1  2  3  6  17  18  25  26  32  89 
enter k
k th smallest element is 33
https://ideone.com/rX130
language:
C (gcc 8.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!