Yes, of course. If there is no such solution between a and b, you can go on "halving" all you like and never get close to a solution. Typically, the problem is to solve f(x)= 0 where f is a continuous function. That is, strictly speaking, the "interval halving" method is a method for solving an equation. To find max or min for the function F(x) means solving F'(x)= 0.
If you can find "a" such that f(a)> 0 and "b" such that f(b)< 0, then you know there exist x such that f(x)= 0 between a and b. One easy "try" is to take c halfway between a and b: c= (a+b)/2. Then evaluate f(c). Of course if it happens that f(c)= 0, you are done. If not, then it is either positive or negative and so different from either f(a) or f(b). That allows you to choose one of those "half size" intervals being assured that there is a solution in that interval. If there is no solution in the initial interval, then both f(a) and f(b) will have the same sign and so will f(c)= f((a+b)/2) so you would have no reason to chose one "half-interval" over the other.