CODEWITHSUNDEEP
c++searchbinarynumbersfibonacci
Narek Margaryan
Narek Margaryan

Reputation: 334

Fibonacci Sequence ,binary search

I am trying to solve the following problem:

F is an infinite sequence of integers that satisfies to Fibonacci condition F(i + 2) = F(i + 1) + F(i) for any integer i. Write a program, which calculates the value of F(n) for the given values of F(i) and F(j).

Input: The input contains five integers in the following order: i, F(i), j, F(j), n. −1000 ≤ i, j, n ≤ 1000, i ≠ j, −2·10^9 ≤ F(k) ≤ 2·10^9 (k = min(i, j, n), …, max(i, j, n)).

Output: The output consists of a single integer, which is the value of F(n).

I am trying to solve this problem by finding F(min(i,j)+1) then using that two neighbors to find F(n). I was told that this can be done by implementing binary search on the interval (-2*10^9,2*10^9) ,but I don't understand how to use binary search here.Could give me a hint or explain the algorithm in a short manner.

Upvotes: 0

Views: 403

Answers (1)

Tomer Arazy
Tomer Arazy

Reputation: 1823

One way I can think of is like that: lets say i < j and F(i) < F(j) so we want to find F(i+1). We know that F(i) < F(i+1) < F(j) so we can do binary search between [F(i),F(j)] - each time we guess F(i+1) and checks if it fits (no easy way around it I think) until you get the correct value.

Complexity - each iteration can take 2000 steps (worst case), and at worst it's going to take be log(4*10^9) iterations which is about 32 so it seems reasonable.

Upvotes: 1

Related Questions