fork(4) download 
  1. /**
  2.  * Complexity:
  3.  * O (logn)
  4.  * 
  5.  * @author javadeveloper
  6.  */
  7. class MedianOfTwoSortedArrays {
  8.  
  9.     private MedianOfTwoSortedArrays() {}
  10.  
  11.     private static boolean isMedian (int[] a1, int[] a2, int pos) {
  12.         if (pos == 0 || pos == (a1.length - 1)) return true;
  13.         return (a1[pos] >= a2[pos]) && (a1[pos] <= a2[pos + 1]);
  14.     }
  15.  
  16.  
  17.     /**
  18.      * Given two sorted arrays of same length it returns the median.
  19.      * If arrays are not of equal length throws the IllegalArgumentException.
  20.      * If arrays are not sorted the results can be unpredictable.
  21.      * 
  22.      * @param a1    the first sorted array
  23.      * @param a2    the second sorted array 
  24.      * @return      the median of the two integers or null if no such median is found due to illegal input.
  25.      */
  26.     public static Double median (int[] a1, int[] a2) {
  27.         if (a1.length != a2.length) throw new IllegalArgumentException("The argument thrown is illegal");
  28.  
  29.         int lb = 0;
  30.         int hb = a1.length - 1;
  31.  
  32.         while (lb <= hb) {
  33.             int a1Median = (lb + hb)/2;
  34.             int a2Median = (a2.length - 1) - a1Median;
  35.  
  36.             if (isMedian(a1, a2, a1Median) || isMedian(a2, a1, a2Median)) {
  37.                 return (a1[a1Median] + a2[a2Median])/2.0;
  38.             }
  39.  
  40.             if (a1[a1Median] < a2[a2Median]) {
  41.                 lb = a1Median + 1;
  42.             }
  43.  
  44.             if (a1[a1Median] > a2[a2Median]) {
  45.                 hb = a1Median - 1;
  46.             }
  47.         }
  48.         return null;
  49.     }
  50.  
  51.     public static void main(String[] args) {
  52.        	int a1[] = {1, 1, 10, 10};
  53.        	int a2[] = {5, 5, 5, 5};
  54.        	System.out.println(median(a1, a2));
  55.     }
  56. }
Success #stdin #stdout 0.07s 381248KB
comments (?)
stdin 
Standard input is empty
stdout 
7.5
https://ideone.com/g3eR1Q
language:
Java (12.0.1)
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!