Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]$ so that $c \in [a_0,b_0]$ and some other function $g$ such that $g(x_1)=g(x_2)$ for all $x_1, x_2 \in [a_0, b_0]$. Also we know $g(x_1) \neq g(x_2)$ if $x_1 \ne x_2$ and either $x_1 \notin [a_0,b_0]$ or $x_2 \notin [a_0,b_0]$. We are not given the numbers $a_0$ and $b_0$.
Suppose we use the standard bisection method to find the root $c$ of $f$. However, we stop when $g(x_1)= g(x_2)$ for two numbers $x_1$ and $x_2$. In fact, the procedure terminates where we find an interval $[x_1, x_2] \subset [a_0, b_0]$ with $c \in [a_0,b_0]$.
Question: What is the complexity of the algorithm? Can we say the algorithm runs in polynomial time?