Beginner
1. Binary Search2. Linear Search3. Fibonacci Search4. Bubble Sort5. Insertion Sort6. Selection Sort7. Quick Sort8. Merge Sort9. Addition of two matrixes10. Subtraction of two matrixes11. Multiplication of two matrixes12. Transpose of given Matrix13. EUCLIDIAN GCD ALGORITHM14. Fabinocci Numbers with matrix multiplication15. Fast Exponential16. Modular inversion17. Prime seiving18. Heap(using array)19. Heapify20. Heap Sort21. Linear Probing22. Open Addressing23. Collision Avoidance24. Binary Search Tree Traversal Techniques25. Finding Kth Largest Element in Binary Tree26. Diameter of a Binary search tree27. Depth of Binary Tree28. Number of Nodes in BST29. Convert Array to Binary Tree30. Convert Array to General Tree31. Lowest Common AncestorFibonacci Search
LEVEL:Beginner
Description
Given a list of integers and a search value. Find the search value from the array using Fibonacci Search Algorithm.
Input Format
First line contains the size of array (n), Second line contains the search value followed by n integers separated by spaces.
Output Format
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
Approach
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