Find Median in Large File of Integers , Java

Find Median in Large File of Integers

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int[] nums = new int[100];
        Random rand = new Random();
        for (int i = 0; i < 100; i++) {
            int num = rand.nextInt(100);
            nums[i] = num;
        }
        Arrays.sort(nums);
        for (int i = 0; i < 100; i++) {
            System.out.print(nums[i] + ",");
        }
        System.out.println(nums[49]);
        System.out.println(nums[50]);
        System.out.println(findMedian(nums));
        System.out.println(findMedian2(nums));
    }
    
    // Find kth smallest number in sorted order
    private static int findKth(int[] nums, int k, int left, int right) {
        if (left >= right) return left;
        int guess = (int) (left + ((long) right - left) / 2);
        int count = 0, max = left, min = right;
        for (int num : nums) {
            if (num <= guess) { 
                count++;
                max = Math.max(max, num);
            } else min = Math.min(min, num);
        }
        if (count == k) return max;
        else if (count < k) return findKth(nums, k, min, right);
        else return findKth(nums, k, left, max);
    }  
    
    private static double findMedian(int[] nums) {
        int len = 0, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int num: nums) {
            len++;
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        if (len % 2 == 1) return (double) findKth(nums, len / 2 + 1, min, max);
        return (double) (findKth(nums, len / 2, min, max) + findKth(nums, len / 2 + 1, min, max)) / 2;
    }
    
    private static double findMedian2(int[] nums) {
        int len = 0, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int num: nums) {
            len++;
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return findMedianHelper(nums, min, max);
    }
    
    private static double findMedianHelper(int[] nums, int lo, int hi) {
        while (lo < hi) {
            int mid = (int) ((long) lo + hi) / 2;
            int len = 0, count = 0;
            int max = lo, min = hi;
            for (int num : nums) {
                len++;
                if (num <= mid) { 
                    count++;
                    max = Math.max(max, num);
                } else min = Math.min(min, num);
            }
            if (count == (len + 1) / 2) return len % 2 == 1 ? max : 0.5*((double) max + min);
            else if (count > (len + 1) / 2) hi = max;
            else lo = min;
        }
        return lo;
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development