[go: up one dir, main page]
Scribd
Upload
98 views3 pages

Fibonacci Search

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1, and was introduced by the mathematician Fibonacci in 1202. Fibonacci Search is an efficient algorithm that uses this sequence to locate a specific element in a sorted array, operating with a time complexity of O(log n). The search process involves generating Fibonacci numbers to define pointers within the array, adjusting them based on comparisons with the target element until the element is found or confirmed absent.

Uploaded by

samyak0023
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
98 views3 pages

Fibonacci Search

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1, and was introduced by the mathematician Fibonacci in 1202. Fibonacci Search is an efficient algorithm that uses this sequence to locate a specific element in a sorted array, operating with a time complexity of O(log n). The search process involves generating Fibonacci numbers to define pointers within the array, adjusting them based on comparisons with the target element until the element is found or confirmed absent.

Uploaded by

samyak0023
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

What is Fibonacci Sequence?

.
The Fibonacci sequence is a series of numbers in which each number is the sum of the two
preceding ones, usually starting with 0 and 1.
It is named after the Italian mathematician Leonardo of Pisa, known as Fibonacci, who
introduced the sequence to Western mathematics in his book “Liber Abaci” in 1202.
The Fibonacci sequence typically begins with the numbers 0 and 1, and each subsequent
number is generated by adding the two previous numbers. The sequence starts as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
.
Here’s how the sequence continues to develop
0+1=1
1+1=2
1+2=3
2+3=5
3+5=8
5 + 8 = 13
8 + 13 = 21
13 + 21 = 34
And so on…
.
Definition of Fibonacci Search
1. Fibonacci Search is an algorithm used to locate a specific element within a sorted
array or list with Fibonacci numbers.
2. It is based on the Fibonacci sequence, a series of numbers where each number is the
sum of the two preceding ones (e.g., 0, 1, 1, 2, 3, 5, 8, 13, 21, …) that I said it earlier.
3. The key idea is to use the Fibonacci numbers to define two pointers ‘left’ and ‘right’,
within the array, which are then adjusted based on comparisons with the target
element until the element is found or it is determined that the element does not exist in
the sorted array.
4. Fibonacci Search method is yet another elimination method where a portion of
the input array is eliminated.
5. Fibonacci Search is known for its time efficiency, typically having a time complexity
of O(log n) for searching in sorted datasets, making it suitable for large arrays or lists.
However, it requires the data to be sorted in ascending order for effective operation.
Algorithm for Fibonacci Search
1. Input a sorted array A[i] with n numbers and target element which we want to
search for.
2. Start by generating a series of Fibonacci numbers until you find a number that is
greater than or equal to the length of the array.
F(k) >= n
Example – if n = 10
Then, fibonacci sequence we have is
0, 1, 1, 2, 3, 5, 8, 13, because 13 >= 10.
3. If F(k) = 0, then stop and print the message
as element not found.
4. Name a variable “offset” = -1
5. Check index i = min(offset + F(k-2), n-1)
6. Compare
If Target Element = A[i],
return i and stop the search
If Target Element > A[i],
k = k-1, offset = i,
repeat step 5 and 6.
If Target Element < A[i],
k = k-2, repeat step 5 and 6.
How does it work?
1. Suppose you have a sorted array and you want to find the number `15`.

Fibonacci Search
.
2. Generate the Fibonacci sequence where F(k) >= n = 11.

Fibonacci sequence
3. F(k) ≠ 0, then search continues
4. Make a variable ‘offset = -1’.
.
Iteration 1
Check i = min (offset + F(k-2), n-1), where k = 7, offset = -1, n = 11
i = min ( -1 + 5, 10)
i = min (4, 10) = 4
Compare the Target Element to Sorted Array
 Target Element = 15, A[4] = 9
 Do k = k-1, offset = 4 and again check for i.
.
Iteration 2
Check i = min (offset + F(k-2), n-1) where k = 6, offset = 4, n = 11.
i = min (4 + 3, 10)
i = min (7, 10) = 7
Compare the Target Element to Sorted Array
 Target Element = 15, A[7] = 15
 Search is successful and return i = 7, the index of the sorted array in which we
found Target Element.

You might also like