2.fibonacci Searching 3z2l21

Fibonacci Search • Fibonacci search is used to search an element of a sorted array with the help of Fibonacci numbers. • Fibonacci number is subtracted from the index thereby reducing the size of the list. • Fibonacci search is a process of searching a sorted array by utilizing divide and conquer algorithm. • Fibonacci search has a complexity of O(log(x))

Fibonacci Search • The Fibonacci number sequence is given by {0,1,1,2,3,5,8,13,21,….} and is generated by the following recurrence relation F0 = 0 F1 = 1 Fi = Fi-1 + Fi-2 • The fibonacci sequence finds an application in a search technique termed fibonacci search

Fibonacci Search • Binary search selects the median of the sublist as its next element for comparison, the fibonacci search determines the next element of comparison as dictated by the fibonacci number sequence • Fibonacci search works only on ordered lists • The number of elements in the list is one less than a fibonacci number n = Fk-1

Decision Tree for Fibonacci Search • The decision tree from Fibonacci search satisfies the following characteristics • If we consider a grandparent, parent and its child nodes and if the difference in index between the grandparent and parent is Fk then (i) If the parent is a left child node then the difference in index between the parent and its child nodes is Fk-1, whereas (ii) If the parent is a right child node then the difference in index between the parent and the child nodes is Fk-2

Decision Tree for Fibonacci Search • Consider an ordered list L={K1, K2,…Kn} where K1 < K2 <… Kn where n = Fk-1 • The fibonacci search decision tree for n=20 where 20 = (F8-1) is shown in figure • The root of the decision tree which is the first element in the list to be compared with key K during the search is that key Ki whose index i is the closest fibonacci sequence number to n • In the case of n=20, K13 is the root since the closest fibonacci number to n=20 is 13.

Decision Tree for Fibonacci Search K13

K8 K5

K3 K2 K4 K6 K1

K7

K18 K11

K10 K9

K16

K20

K12 K15 K17 K19 K14

Decision Tree for Fibonacci Search • Algorithm illustarates the procedure for fibonacci search • N is the number of data elements is such that (i) Fk+1 > (n+1) and (ii) Fk = (n+1) for some m>=0 where Fk+1 and Fk are two consecutive fibonacci numbers

Algorithm for Fibonacci Search Procedure Fibonacci_search(L,n,K) // L(1:n) is a linear ordered (non decreasing) list of data elements. N is such that Fk+1>(n+1). Also Fk+m=(n+1). K is the key to be searched in the list // Obtain the largest fibonacci number Fk closest to n+1 p= Fk-1 q=Fk-2 r=Fk-3 m=(n+1) – (p+q) If (K>L(p)) then p=p+m Found=false

Algorithm for Fibonacci Search While ((P<>0) and (not found)) do Case : K=L[p] { print (“key found”); found=true; } : K L[p] : if (q=1) then p=0 else {p=p+r; q=q-r; r=r-q} Endcase Endwhile If (found=false) then print (“key not found”); End fibonacci_search.

Algorithm for Fibonacci Search • Let us search for the key K=434 • L=(2,4,8,9,17,36,44,55,81,84,94,116,221,256,3 02,256,396,401,434,536) • N=20, the number of elements is such that (i) F9 > n+1 and (ii) F8+m = (n+1) where m=0 and n=20 • The algorithm for fibonacci search first obtains the largest fibonacci number closest to n+1. ie F8 in this case.

Algorithm for Fibonacci Search • It compares K=434 with the data element with index F7 i.e.L[13]=221 • Since K>L[13] the search list is reduced to L[14:20]={256,302,356,396,401,434,536} • Now K compares itself with L[18]=401. Since K>L[18] the search list is further reduced to L[19:20]={434,536} • Now K is compared with L[20]=536. Since K
Algorithm for Fibonacci Search Search key K

< K=L[p] >

t

p

q

r

Remarks

13

8

5

n=20 m=0 since F8+0=n+1

K > L[13] = 221

13

8

5

Since K > L[p] p=p+m

K > L[13] = 221

18

3

2

K > L[18} = 401

20

1

1

19

1

0

434

K < L[20] = 536 K = L[19] = 434

1

Key is Found

Algorithm for Fibonacci Search Search key K

< K=L[p] >

t

66 K > L[13] = 221

8

K > L[8] = 55

p

q

r

Remarks

13

8

5

n=20 m=0

8

5

3

11

2

1

K < L[11] = 94

2

10

1

1

K < L[10] = 84

1

9

1

0

K < L[9] = 81

Since (r=0) p is set to 0 Key is not found

Fibonacci Search • An advantage of fibonacci search over binary search is that while binary search involves division which is computationally expensive, during the selection of next element for key comparison, fibonacci search involves only addition and subtraction