Recursion algorithms pseudocode [duplicate]

Question

I want to create a recursion pseudocode that will executed in O(logn) complexity and i want it to find the lower f(i) < 0 and f[1....n] which f(1) >0 and f(n)<0

prodedure fanc(A[n] , p , q )  //(this is my array,first digit of A ,last digit of A)
if A[n/2] >= 0
     return fanc(A[n/2] , A[n/2] , A[n-1])
else
     return fanc(A[n/2] , A[0] , A[n/2 -1])
if p<q
   print p
else
   print q

I know that somehow i have to end the recursion. Also i would like to know if i am in the correct path and if u have any good thoughts for this problem!

Better text of assignment copied from https://stackoverflow.com/questions/42935621/algorithm-in-ologn:

Let an integer function f:{1,2,3...n} be monotonic and defined in {1,2,3...n} and suppose that f(1) > 0 and f(n) < 0. We would like to find the smallest integer i with f(i) < 0. Design an algorithm for this purpose that run in O(logn).

Can you expand on the description of your problem and add a couple of simple examples? Generally, end the recursion when you reach a problem that is trivially solvable, such as 1! when computing the factorial. Test for it with an if statement inside the procedure. — Svaberg
– Svaberg, Commented Mar 26, 2017 at 1:34
Same as stackoverflow.com/questions/42935621/algorithm-in-ologn ? This question has appeared multiple times this week. — Paul Hankin
– Paul Hankin, Commented Mar 26, 2017 at 1:43
@Svaberg the description its same as the question Paul Hankin has provide! stackoverflow.com/questions/42935621/algorithm-in-ologn .Yeah i know but i not sure how i can built in my algorithm! I will in the procedure do something like a flag that will be true and stop the recursion when my algorithm has reach the solvable sub-problem? I want and i dont know if is builtable to define in which solvable problem i want to stop. I hope you understand what i want to say — Mikel
– Mikel, Commented Mar 26, 2017 at 1:57
Mikel, you could search for "binary search recursive". For your problem, I suggest you write actual code rather than pseudocode since then you can run it and test it. — Paul Hankin
– Paul Hankin, Commented Mar 26, 2017 at 2:17
@PaulHankin Yeah i know the binary search algorithm i have understand the way he search and find the solution.. But here as you said i use monotony and i cant understand how the monotony sort the algorithm ! In my problem i tried to sort my array inspired from binary search algorithm but i cant cause binary search algorithm knows what is it searching (i mean the number) me i dont know this number it will be everything that is <0 ! Also i cant divide my algorithm in half cause i dont know if the half is where numbers change from >0 to <0 . I didnt questioned right in my first question sorry — Mikel
– Mikel, Commented Mar 26, 2017 at 2:24

maraca · Accepted Answer · 2017-03-26 03:30:14Z

2

You are almost there, you have to make it relative to p and q (from and to) not n. Then if from == to you found a solution. This assumes that there is always a solution in the range [1 ... n].

function firstNegative(f, from, to) {
    if (from == to)
        return from;
    next = from + (to - from) / 2;
    if (f(next) >= 0)
        return firstNegative(f, next + 1, to);
    else
        return firstNegative(f, from, next);
}
print firstNegative(f, 1, n);

answered Mar 26, 2017 at 3:30

maraca

9,5873 gold badges27 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Mikel Over a year ago

thank you for your answer! Can you explain me why you create the next variable? It seems little differrent from a binary search in recursion am i wrong?

maraca Over a year ago

The next variable is the middle between from and to. It is only to/2 when from is 0.

Mikel Over a year ago

Okey! Thank you!!

maraca Over a year ago

You're welcome. Contrary to the other question you showed what you've tried. Don't get discouraged by the downvotes.

Mikel Over a year ago

I think that you gave me the answer! I wanted to use the binary search algorithm to have O(logn) complexity and wanted to find the first negative number i meet in my monotonic function..I didn't know how to stop my recursion and you helped me with that! Im not getting discouraged by the downvotes im new in programming world and some maybe are easy to most of them but not yet for me

Collectives™ on Stack Overflow

Recursion algorithms pseudocode [duplicate]

1 Answer 1

5 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Linked

Related