fork(1) download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. class MedianOfTwoArrays {
  4. 	public static void main(String[] args) {
  5. 		// Note: These are sorted arrays and are of equal length.
  6.  
  7. 		int[] array1 = {1, 3, 5, 7, 9, 11}; // median is 6
  8. 		int[] array2 = {2, 4, 6, 8, 10, 12};
  9.  
  10.  
  11. 		int median = getMedianOfTwoArrays(array1, array2);
  12. 		System.out.println(median);
  13. 	}
  14.  
  15. 	static int getMedianOfTwoArrays(int[] array1, int[] array2) {
  16. 		int index1 = array1.length/2;
  17. 		int index2 = array2.length/2;
  18.  
  19. 		int m1 = array1[index1];
  20. 		int m2 = array2[index2];
  21.  
  22. 		if(m1 == m2) {
  23. 			return m1;
  24. 		} else {
  25. 			return findMedian(array1, array2, 0, array1.length - 1, 0, array2.length - 1);
  26. 		}
  27. 	}
  28.  
  29. 	static int findMedian(int[] array1, 
  30. 							int[] array2,
  31. 								int low1, 
  32. 									int high1,
  33. 										int low2, 
  34. 											int high2) {
  35. 		// termination condition
  36. 		System.out.print(low1); System.out.print(high1);System.out.print(low2);System.out.println(high2);
  37. 		if((high1 - low1 + 1) == 2 && (high2 - low2 + 1) == 2) {
  38. 			return (Math.max(array1[low1], array2[low2]) + Math.min(array1[high1], array2[high2]))/2;
  39. 		}
  40.  
  41.  
  42.         assert (high2-low2==high1-low1); // sanity check
  43.         int n=high1-low1+1; // "n" from logic
  44.  
  45.         int m1 = median(array1,low1,high1);
  46.         int m2 = median(array2,low2,high2);
  47. 		System.out.println("Median 1:"+m1);
  48. 		System.out.println("Median 2:"+m2);
  49.  
  50.         int low1_t = 0;
  51.         int high1_t = 0;
  52.         int low2_t = 0;
  53.         int high2_t = 0;
  54.  
  55.         if(m1 == m2) {
  56.             return m1;
  57.         } else if(m1 > m2) {
  58.             if (n % 2 == 0) {
  59.                 low1_t = low1;
  60.                 high1_t = high1-n/2+1;
  61.                 low2_t = low2+n/2-1;
  62.                 high2_t = high2;
  63.             } else {
  64.                 low1_t = low1;
  65.                 high1_t = high1-n/2;
  66.                 low2_t = low2+n/2;
  67.                 high2_t = high2;
  68.             }
  69.         } else {
  70.             if (n % 2 == 0) {
  71.                 low1_t = low1+n/2-1;
  72.                 high1_t = high1;
  73.                 low2_t = low2;
  74.                 high2_t = high2-n/2+1;
  75.             } else {
  76.                 low1_t = low1+n/2;
  77.                 high1_t = high1;
  78.                 low2_t = low2;
  79.                 high2_t = high2-n/2;
  80.             }
  81.         }
  82.         return findMedian(array1, array2, low1_t, high1_t, low2_t, high2_t);
  83. 	}
  84. 	static int median(int[] arr, int low,int hig) 
  85. 	{
  86. 		if ((low+hig)%2 == 0) return arr[(low+hig)/2];
  87. 		int mid=(low+hig)/2;
  88. 		return (arr[mid]+ arr[mid-1])/2;
  89. 	}
  90. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin 
Standard input is empty
stdout 
0505
Median 1:4
Median 2:5
2503
Median 1:6
Median 2:3
2413
Median 1:7
Median 2:6
2323
6
https://ideone.com/zY30Vg
language:
Java (HotSpot 12)
created:
10 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!