0
$\begingroup$

I need some help with a problem. I have currently an algorithm. This algorithm gives me a true or false for a variable which I need to iterate( e. g. From 0 to 100} . Till now I solved it with a brute force method. So I just enhance the variable by a factor, enter the variable to the algorithm till I get a true. This really needs a lot of run time. Then I switched to the bisection method. Here I had the problem that sometimes the function is true for some values and then switches again to false. This means if the area is before the half of the interval, the bisection method can not find the area before because the bisection method doesn't get the true in therefore took the second half of the interval.

My question is now: does sb has an idea how I could fix that? Are there any search algorithms which are exactly for that problem?

$\endgroup$
  • 4
    $\begingroup$ There is not much you can do if you do not assume any property about your function. What do you know? I assume it must return true for at least one value, to begin with. What else do you know? If it can return true for exactly a single value then you're basically stuck with linear search. $\endgroup$ – Steven Oct 3 '19 at 19:56
0
$\begingroup$

With no other given assumptions, it is a linear solution in the most optimal scenario. One can have better solution (binary search) in problems where all the values after first true are true. But if there is only one element, it is a O(n) solution.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.