This is an step by step animation of Fibonacci Search Algorithm using the Tkinter and Turtle graphics libraries in Python.The purpose of the project is to demonstrate the Fibonacci search algorithm, a search technique based on the Fibonacci sequence, through an animated representation. The user can input an array size, elements for the array, and a target element to be searched. Here is the working of the Animation with an Example: Size of the input array is 10. The smallest Fibonacci number greater than 10 is 13.Therefore, Fib = 13, Fib_m1 = 8, Fib_m2 = 5. We initialize offset = -1
In the first iteration, compare it with the element at index = minimum (offset + Fib_m2, n – 1) = minimum (-1 + 5, 9) = minimum (4, 9) = 4.
The fourth element in the array is 20, which is not a match and is less than the key element.
In the second iteration, update the offset value and the Fibonacci numbers.Since the key is greater, the offset value will become
the index of the element, i.e. 4. Fibonacci numbers are updated as Fib= Fib_m1 = 8,Fib_m1 = 5, Fib_m2 = 3.
Now, compare it with the element at index = minimum (offset + Fib_m2, n – 1) = minimum (4 + 3, 9) = minimum (7, 9) = 7.
Element at the 7th index of the array is 43, which is not a match and is also lesser than the key.
We discard the elements after the 7th index, so n = 7 and offset value remains 4.
Fibonacci numbers are pushed two steps backward, i.e. Fib = Fib_m1 = 3.
Fib_m1= 2, Fib_m2= 1.
Now, compare it with the element at index = minimum (offset + Fib_m2, n – 1) = minimum (4 + 1, 6) = minimum (5, 7) = 5.
The element at index 5 in the array is 24, which is our key element. 5th index is returned as the output for this example array.
