I thought this question had an interesting flavor to it despite the non-uniqueness discussed in joriki's post. So I'll not worry about that, and instead I'll just consider the task of finding a 'median'. I think this numerical method-like approach will work well.
I have different methods for odd and even numbers of points on the circle. Odd is easier. I think we can quickly agree that for an odd number of points, a median must either lie on a point or lie diametrically opposed to a point (otherwise, an odd number of points can never be cut into two portions of the same parity). We can also see that these two cases are equivalent, and that what we're really looking for is a median-chord, i.e. a diameter of the circle that puts half of the points on one side and the other on the other. So just test all of the points, and you'll find a median.
Now suppose we have an even number of points on the circle. This is the more entertaining part. To examine this part, I would like to describe a process and rely on a sort of discrete intermediate value property.
Suppose we reformulate the problem as drawing a diameter, as I mentioned above, and counting the number of points on each side. Further, associate one side of the diameter with positive values and the other with negative, and call the Sum the sum of these two (one positive, one negative) numbers. We look for when the Sum is zero. Then the process of rotating the diameter follows a sort of discrete intermediate value property, where the Sum will change in absolute value by 0, 1, or 2 only. 1 can only happen when the diameter lies on a point.
Now, for the process itself. Calculate the Sum from the diameter at each of the even points. If any of these results in a Sum of zero, then we are done (use that diameter). If not, then there exists a positive Sum point adjacent to a negative Sum point. Then such a diameter passes through the space between these two points. Fortunately, only a finite number of spots need to be checked - only where the diameter crosses over a point (in this case, on the opposite side, and you should really just look at their Sums instead, but so be it).
Finally, I want to note that there does always exist a median. And I wanted to note that while writing this up, I didn't end up using the IVP nearly as much as I thought I would.