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;
        }
        double median = findMedian(nums);
        Arrays.sort(nums);
        for (int i = 0; i < 100; i++) {
            System.out.print(nums[i] + ",");
        }
        System.out.println();
        int l = nums[49];
        int r = nums[50];
        System.out.println("l: " + nums[49] + ", r:" + nums[50] + ", m: " + median);
        if(median != (double)(l + r) / 2.0)
            System.out.println("false");
        System.out.println("{3, -2, 7} median (3.0) : " + findMedian(new int[]{3, -2, 7}));
        if(3.0 != findMedian(new int[]{3, -2, 7}))
            System.out.println("false");
        System.out.println("{-100, 99, 3, 0, 5, 7, 11, 66, -33} median (5.0): " + findMedian(new int[]{-100, 99, 3, 0, 5, 7, 11, 66, -33}));
        if(5.0 != findMedian(new int[]{-100, 99, 3, 0, 5, 7, 11, 66, -33}))
            System.out.println("false");
        System.out.println("{4, -100, 99, 3, 0, 5, 7, 11, 66, -33} median (4.5): " + findMedian(new int[]{4, -100, 99, 3, 0, 5, 7, 11, 66, -33}));
        if(4.5 != findMedian(new int[]{4, -100, 99, 3, 0, 5, 7, 11, 66, -33}))
            System.out.println("false");

}
    
    private static long search(int[] nums, int k, long left, long right) {
            if (left >= right) {
                return left;
            }

long res = left;
            long guess = (left + right) / 2; //left + (right - left) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= guess) {
                    count++;
                    res = Math.max(res, num);
                }
            }

if (count == k) {
                return res;
            } else if (count < k) {
                return search(nums, k, Math.max(res + 1, guess), right);
            } else {
                return search(nums, k, left, res);
            }
        }

public static double findMedian(int[] nums) {
            int len = 0;
            for (int num : nums) {
                len++;
            }

if (len % 2 == 1) {
                return (double) search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
            } else {
                return (double) (search(nums, len / 2, Integer.MIN_VALUE, Integer.MAX_VALUE) +
                        search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE)) / 2;
            }
        }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development