Recursion algorithms pseudocode

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, Mar 26 '17 at 01:34
Same as http://stackoverflow.com/questions/42935621/algorithm-in-ologn ? This question has appeared multiple times this week. — Paul Hankin, Mar 26 '17 at 01:43
@Svaberg the description its same as the question Paul Hankin has provide! http://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, Mar 26 '17 at 01: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, Mar 26 '17 at 02: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, Mar 26 '17 at 02:24
@maraca I dont know if i understand right! But if the x is the solution in my array i want yeah f(x-1) >=0 so x be the first and lower negative number in my array! And i want to do all this in O(logn) complexity which means no reading..just dividing my array until find the solution..And thats my problem most of sorting algorithms run in O(nlogn) complexity — Mikel, Mar 26 '17 at 03:17

score 2 · Accepted Answer · answered Mar 26 '17 at 03:30

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 '17 at 03:30

maraca

8,468
3
23
45

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? – Mikel Mar 26 '17 at 04:19
The next variable is the middle between from and to. It is only to/2 when from is 0. – maraca Mar 26 '17 at 12:47
Okey! Thank you!! – Mikel Mar 26 '17 at 12:56
You're welcome. Contrary to the other question you showed what you've tried. Don't get discouraged by the downvotes. – maraca Mar 26 '17 at 13:09
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 – Mikel Mar 26 '17 at 13:37

Recursion algorithms pseudocode

1 Answers1