How do you find a median without using lists?

Question

My teacher wants me to find the median of 10 inputs from the user by using iterations.

This is how I used iterations to find the sum, number of odd numbers, the max, and the number of prime numbers. But I'm stuck on finding the median.

def Main(): #main function
    sum=0
    odd=0
    temp=0
    prime=0
    median=0

    for i in range(10):
        x=float(input("Please enter a number")) #ask user for input 10 times
        sum=sum+x #adds all inputs together
        if x%2!=0: #all even numbers are divisible by 2
            odd=odd+1
        if x>=temp: #update temp with current largest input
            temp=x
        for p in range (2,int(math.sqrt(x))+1):#find prime numbers
            if x>=2 and x%p==0: prime=prime+1

Providing code was good, but how about a test data set, and what your code claims the median is? — benc, Nov 03 '18 at 06:08
Why is the requirement "without using lists"? That doesn't make sense. — roganjosh, Nov 03 '18 at 06:22
I'd just use a `set()` to wind them up :) Seems a silly requirement tbh with no practical outcome. Please remove one of the python tags so we know what version you're using. — roganjosh, Nov 03 '18 at 06:28
To the downvoters; the requirement was set by the teacher and makes little sense to me. I don't see any issue with the question itself. Please consider this when benchmarking the question against the rest of the Python feed right now. — roganjosh, Nov 03 '18 at 06:49
My comment is not related to the question but please also check your code for finding the number of primes. It does not seem correct. — Lax_Sam, Nov 03 '18 at 07:38
Store your data in a numpy array (not a list) and use [`np.median()`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.median.html). That will teach them to come up with ridiculous restrictions. — Mr. T, Nov 03 '18 at 10:21
To find the median of 10 unordered numbers, you have to sort them and compute the mean of the 5th and 6th number. So you have to store all of the input numbers somewhere. You could emulate a list with a dictionary `d={}`, `d[i]=x` and use `math.mean(sorted(d.keys())[4:6])` to get the median, but `sorted` returns a list, so you would still kind of use a list. Maybe a `collections.OrderedDict` or a `numpy.ndarray` are alternative options, but they all would only be used to provide a list-like data structure. — Niklas Mertsch, Nov 03 '18 at 10:26

score 0 · Answer 1 · answered Nov 03 '18 at 09:44

0

import math

def Main(): #main function
    sum=0
    odd=0
    temp=0
    prime=0
    median=0
    my_list =[]
    for i in range(10):
        x=float(input("Please enter a number: ")) #ask user for input 10 times
        sum=sum+x #adds all inputs together
        if x%2!=0: #all even numbers are divisible by 2
            odd=odd+1
        if x>=temp: #update temp with current largest input
            temp=x
        for p in range (2,int(math.sqrt(x))+1):#find prime numbers
            if x>=2 and x%p==0: prime=prime+1

        my_list.append(x)
        my_list.sort()
        size =len(my_list)
        if size == 1:
            median = my_list[0]
        elif size % 2 == 0:
            size = int(size/2)
            median=(my_list[size-1]+my_list[size])/2
        else:
            median = my_list[int(size / 2)]

        print("sum is ", sum, ",odd is ", odd, ",temp is ", temp, ",prime is ", prime, "median is ", median)

Main()

answered Nov 03 '18 at 09:44

Mohammad reza Kashi

321
1
5
17

Answering the question "How do you find a median without using lists?" by using a list is not very helpful. – Niklas Mertsch Nov 03 '18 at 14:55
I think you can't calculate median without list and sorting. – Mohammad reza Kashi Nov 05 '18 at 08:23
have you got any reference for it? – Mohammad reza Kashi Nov 05 '18 at 08:24
I have no idea, just pointing out that your answer does not answer the question. – Niklas Mertsch Nov 05 '18 at 08:51
yesterday i spent about 2 hours in internet and books bout i could not find any algorithm for calculate median without list and sort it. – Mohammad reza Kashi Nov 05 '18 at 08:57
I did not say that it is possible, I just said that your answer obviously does not answer the question. OP explicitly asked for a solution without list, and you answer by using a list. If you don't know the answer, don't post one, and if you know that there is no answer, post it as a comment. – Niklas Mertsch Nov 05 '18 at 17:03

score 0 · Answer 2 · answered Nov 03 '18 at 10:10

First of all, as a user pointed out in a comment to your question, your method to determine prime numbers is not correct. You only should increase that counter after all factors have been checked, not after each one.

There are a few questions on StackOverflow that show how to calculate primes in python; here is a slightly improved version of your code with that error fixed (and some style improvement suggestions):

def main():
    sum = 0
    counter_odd = 0
    max_num = None
    min_num = None
    counter_prime = 0
    median = 0

    for i in range(10):
        x = float(input("Please enter a number"))

        sum += x

        if x % 2 != 0:
            counter_odd += 1

        if max_num is None or max_num < x:
            max_num = x
        if min_num is None or min_num > x:
            min_num = x

        if x == 0 or x == 1:
            counter_prime += 1
        elif x > 1:
            if not any(x % d == 0 for d in range(2, int(math.sqrt(x)) + 1)):
                counter_prime += 1

As to your main question: there are several questions on SO about finding medians in unsorted lists (that would be very similar to searching for medians without having the whole list at the beginning). Maybe search for that without the Python tag, so you get to see some algorithms without tying to a specific language.

For example, in this question you can find the suggestion to use the median of medians approach (Wikipedia).

How do you find a median without using lists?

2 Answers2