Array ( [0] => [1] => questions [2] => HackwithInfy-Previous-Questions [3] => Fibonacci-Search )
Given a list of integers and a search value. Find the search value from the array using Fibonacci Search Algorithm.
First line contains the size of array (n), Second line contains the search value followed by n integers separated by spaces.
Print the index of the search value if present else print 1.
5 3 5 2 3 4 1
2
6 28 34 46 33 25 67 45
-1
6 32 32 466 353 257 65 45
0
Login to see Discussion
Step-i) Find the smallest Fibonacci Number(mth number) greater than or equal to Search Value.
Step-ii) While the array elements are to be inspected, Compare the search value with the last element of range covered by (m-2) element.
Step-iii) If search value matches the element, return the index of the element.
Step-iv) If less than the element move the three Fibonacci variables two Fibonacci down else greater than the element move the three Fibonacci variables one Fibonacci down.
Step-v) Repeat ii,iii,iv. If element is not found return -1 and terminate.
Time Complexity: O(log(n))
Space Complexity: O(log(n))
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution