How to find the median of n values Without using Arrays (or list or any other collection/ function that uses arrays/list)?

Question

Scenario:

The user is supposed to enter N (the number of values) followed by N values.

How can I output the median?

Answer 1

You definitely need some storage for at least N/2 places. There's no way around that.

EDITED after OP's coment:

Get some good course on programming, esp. data structures. You can't rely on Stackoverflow for all your developer career ;-). Having said that, let's give you a starting point: I'd use an ArrayList here:

int n = ...; // get N from the user;
List<Double> list = new ArrayList<Double>();
for (int i=0; i<n; i++) {
    double element = ...; // get element from the user;
    list.add(element);
}
// Have the Java library sort the list for you
Collections.sort(list);
// now pick/compute the median from the sorted list
// I'll leave that up to you..

Answer 2

I suggest that you hand program a binary tree. You probably need to allow duplicates, to Java’s built in TreeSet won’t do. It may also be that you can find a suitable tree implementation somewhere on the net. The tree should be sorted. See Binary search tree on Wikipedia for more inspiration.

Your main program will read your numbers one by one and insert them into your tree. After that, it will query the tree for the middle element, or two middle elements if N is even.

You don’t need any array to implement your tree. For finding the ith element, the tree will perform an inorder traversal counting the elements encountered and returning the ith element.

Answer 3

Without Array, without List, or any other Collection.

    try (Scanner scanner = new Scanner(System.in)) {
        System.out.print("Number of numbers: ");
        int N = scanner.nextInt();
        System.out.printf("Enter the %d numbers: ", N);
        double median = IntStream.range(0, N)
                .mapToDouble(i -> scanner.nextDouble())
                .sorted()
                .skip((N-1)/2)
                .limit(2-N%2)
                .average()
                .getAsDouble();
        System.out.printf("The median is %f%n", median);
    }

(Pay no attention to that man behind the .sorted() curtain.)