Given a set of points $X \subset \mathbb{R}$, one can define the median $m^*$ using optimization.
Namely $m^* = \textbf{argmin}_{m \in \mathbb{R}} \sum_{i \in X} |i - m|$. Here $|.|$ is absolute value. As $m^*$ could not be uniquely define, there could be an interval of $m$ all minimize the function, then apply a $min$ would be my fix to it. The reason behind that is i also care about the minimum value of such objective function, all the $m^*$ would gives the same value.
What if a set of points $Y \subset S^1$ from 1-sphere ?
I can still define the median $n^*$ as $n^* = \textbf{argmin}_{n \in S^1} \sum_{j \in Y} |j - n|$. Here $|.|$ is the shortest distance along the circle between two points. Similarly if there exists an interval of $n$ all minimize the objective, pick the minimum as the desired value. (or any feasible $n$ if that is more efficient)
Is the $n^*$ going to be the conventional median? How can I efficiently find such median?
Your definition of the median isn't actually uniquely defined even in the $X \subset \mathbb{R}$ case if $X$ has a (finite) even number of points. Any number $m$ between the middle two values of $X$ will minimise your optimisation problem. Similarly, the median isn't necessarily uniquely defined in $S^1$ when you define it that way. In particular, if you have an even number of evenly spaced points, then every point in $S^1$ is a median by your definition.
In general, I think you can say that $m\in S^1$ is a local minimum of your objective if and only if there are the same number of points in the clockwise half-circle from $m$ as there are in the anticlockwise half-circle. This will be constant on intervals where there aren't any points in $X$ or any points opposite a point in $X$. So you just need to create a copy $X'$ of $X$ shifted halfway around the circle, then for each interval between points in $X \cup X'$, count the points of $X$ in the half-circles on each side of (any point in) that interval.