fork(4) 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. 		int[] array1 = {1, 3, 5, 7, 9, 11}; // median is 6
  7. 		int[] array2 = {2, 4, 6, 8, 10, 12};
  8.  
  9. 		int median = getMedianOfTwoArrays(array1, array2);
  10. 		System.out.println("Median is: " + median);
  11. 	}
  12.  
  13. 	static int getMedianOfTwoArrays(int[] array1, int[] array2) {
  14. 		int index1 = array1.length/2;
  15. 		int index2 = array2.length/2;
  16.  
  17. 		int m1 = array1[index1];
  18. 		int m2 = array2[index2];
  19.  
  20. 		if(m1 == m2) {
  21. 			return m1;
  22. 		} else {
  23. 			return findMedian(array1, array2, 0, array1.length - 1, 0, array2.length - 1);
  24. 		}
  25. 	}
  26.  
  27. 	static int findMedian(int[] array1, 
  28. 							int[] array2,
  29. 								int low1, 
  30. 									int high1,
  31. 										int low2, 
  32. 											int high2) {
  33. 		// termination condition
  34. 		// System.out.println("low1: " + low1 + "\thigh1: " + high1 + "\tlow2: " + low2 + "\thigh2: " + high2);
  35.  
  36. 		if(2 == (high1 - low1 + 1) && 2 == (high2 - low2 + 1)) {
  37. 			return (Math.max(array1[low1], array2[low2]) + Math.min(array1[high1], array2[high2]))/2;
  38. 		}
  39.  
  40. 		int length = high1 - low1 + 1;
  41.  
  42. 		int m1 = median(array1, low1, high1);
  43. 		int m2 = median(array2, low2, high2);
  44. 		// System.out.println("Median-1: " + m1 + "\t Median-2: " + m2 + "\n");
  45.  
  46. 		int low11 = 0;
  47. 		int high11 = 0;
  48. 		int low12 = 0;
  49. 		int high12 = 0;
  50.  
  51. 		if(m1 == m2) {
  52. 			return m1;
  53. 		} else if(m1 > m2) {
  54. 			if(length % 2 == 0) {
  55. 				low11 = low1;
  56. 				high11 = high1 - length/2 + 1;
  57. 				low12 = low2 + length/2 - 1;
  58. 				high12 = high2;	
  59. 			} else {
  60. 				low11 = low1;
  61. 				high11 = high1 - length/2;
  62. 				low12 = low2 + length/2;
  63. 				high12 = high2;
  64. 			}
  65. 			return findMedian(array1, array2, low11, high11, low12, high12);
  66. 		} else {
  67. 			if(length % 2 == 0) {
  68. 				low11 = low1 + length/2 - 1;
  69. 				high11 = high1;
  70. 				low12 = low2;
  71. 				high12 = high2 - length/2 + 1;
  72. 			} else {
  73. 				low11 = low1 + length/2;
  74. 				high11 = high1;
  75. 				low12 = low2;
  76. 				high12 = high2 - length/2;
  77. 			}
  78. 			return findMedian(array1, array2, low11, high11, low12, high12);
  79. 		}
  80. 	} // method
  81.  
  82. 	static int median(int[] array, 
  83. 						int low, 
  84. 							int high) {
  85. 		if((low + high) % 2 == 0) {
  86. 			return array[(low + high) / 2];
  87. 		} else {
  88. 			int mid = (low + high)/2;
  89. 			return (array[mid] + array[mid - 1])/2;
  90. 		}
  91. 	}
  92.  
  93. }
Success #stdin #stdout 0.1s 320256KB
comments ()
stdin 
Standard input is empty
stdout 
Median is: 6
https://ideone.com/FfzexO
language:
Java (HotSpot 12)
created:
9 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!