I'm having some convex set $P \subset \mathbb{R}^n_+$ and a linear-time indicator procedure $I_P(x)$ that allows for each given point $x \in \mathbb{R}^n_+$ to say whether it lies inside $P$ or not.
It's required to find such $x^{*} \in P$ that has minimal euclidean norm.
Nothing can be said about the nature of the set $P$ except that it is convex and its indicator function is considered as a some kind of "black box".
How can I calculate the $x^*$?
In $\mathbb{R}^2$ everything is simple: we can use some kind of bisection.
Your problem amounts to the computation of the euclidean projection of the origin $0$ onto the set $P$. There is no general rule for computing this. It all depends on the geometry of $P$, and nothing you've said allows for any simplification of the general problem.