'What exactly is the "i" in this median task?
Hey i have the task to write a code to compute the median from an array. I My teacher gave me the following instructions:
Algorithm for the list l with length n > 1 and the position i:
divide the n elements from the list L in ⌊n/5⌋ groups with 5 elements and <= 1 group with n mod 5 elements.
compute the median from each of the ⌈n/5⌉ groups
compute recursively the median x of the medians from step 2
partition the list L in 2 lists L1 with all numbers < x and L2 with all numbers > x. Also compute the length l1 and l2 of the lists (x will be on the position k = l1 + 1)
if i = k return x, if i < k compute the first element of L1 recursively and if i > k compute the (i-k)th element in L2 recursively.
So my question is, what exactly is the "i"? i already wrote the code and everything is working good, except step 5 because i don't know what the i is and how to use it. How is it defined and how does it change in the recursion?
Solution 1:[1]
This is honestly a too much common term in programming and also a very basic concept. Here, 'i' means current index. So, for instance, if you're on the index 4 and l1 is 3 then i == k (as it's mentioned before that k = l1 + 1), you have to return x!
Solution 2:[2]
The algorithm you’ve listed solves the following problem:
Given an (unsorted) array A and an index i, return the ith smallest item in array A.
So, for example, if you have an array A of length 5, then if i = 0 you’re asking for the smallest element in the array, if i = 2 you’re asking for the median, and if i = 4 you’re asking for the largest element of the array.
(This use of the variable i is specific to the problem statement as it was given to you. It’s not something that generally has this meaning.)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Muntaha Islam |
| Solution 2 | templatetypedef |