0

Possible Duplicate:
Efficiently finding the ranks of elements in an array?

If I have an array of elements A [0 to 15], and I know that the median is in the range A[8..11]. How can I find the median of all the elements in A by picking it from A[8..11]? What will its rank be? I've been reading a lot about this but I couldn't find an answer to this specific question. Any help is appreciated. The array basically contains 2D points, and I want to split the points into rectangular regions.

Community
  • 1
  • 1
hadilnc01
  • 25
  • 4
  • I've been stuck on this for a couple of months now and still I wasn't able to find a specific way to know the rank of the median in A[8..11] – hadilnc01 Oct 27 '12 at 23:38
  • I'm not sure that's a dupe btw. That question asks how to find ranks without touching the original array but still being able to see it all. This one has the restriction of not seeing the entire array. – paxdiablo Oct 28 '12 at 00:01
  • @Neil I don't want to scan all the elements to find the median, I know it's in A[8..11]. If I wanted to scan them all, I would've done the generic median finding algorithm. – hadilnc01 Oct 28 '12 at 09:18
  • okay this is the paper that I've been reading and got me stuck on this problem: Cache oblivious data structures for orthogonal range searching. This paper basically is explaining how to build CO kd tree. In section 2.2.2, after dividing the points into rectangular regions to form a grid, we have to find the median point in order to divide the points into 2 subsets. In section 2.2.2 they're explaining how to find the median and it has something to do with my question. I hope this makes it clearer. – hadilnc01 Oct 28 '12 at 09:19

3 Answers3

2

You can't know the median of a set of elements simply by observing a subset of those elements. The median is dependent on each and every element of the entire set.

Kenogu Labz
  • 1,094
  • 1
  • 9
  • 20
1

I don't think you can. The median is the data element that splits the data in two, when sorted.

If it's sorted, that will usually be the mean of data[7] and data[8] for a data[0..15] array.

If it's not sorted, there's no way to find it without examining all the elements.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
0

If you want to split an array into two sets of "small" and "large" values, the easiest way is to sort the array. If you don't want to sort the whole array, then you can use a modified quicksort: once you have partitioned the array, only sort the half of the array that contains the median (unless the partition turned out to be the median, in which case you can stop).

Neil
  • 54,642
  • 8
  • 60
  • 72