Fibonacci

Search
DR. C. SIVARAJ
Fibonacci Search

• Fibonacci search is an efficient search algorithm based

on divide and conquer principle that can find an element in
the given sorted array with the help of Fibonacci series

• O(log N) time complexity.

 Fibonacci Search
• This is based on Fibonacci series which
is an infinite sequence of numbers
0,1,1,2,3,5,8,13....
denoting a pattern which is captured by
the equation: F(0) = 0
F(n+1)=F(n)+F(n-1) F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
• where F(i) is the i number of the
th
F(3) = F(2) + F(1) = 1 + 1 = 2
Fibonacci series where F(0) and F(1) are F(4) = F(3) + F(2) = 1 + 2 = 3
defined as 0 and 1 respectively.
and so continues the series
• The first few Fibonacci numbers are:
0,1,1,2,3,5,8,13....
 Fibonacci search
• Unlike binary search, Fibonacci search different is that it
divides the array in unequal parts

• operations involved in this search are

• addition
• subtraction

• which means light arithmetic operations takes place and

hence reducing the work load of the computing machine.
Fibonacci Search Algorithm

• Step 1: Firstly, we need to find F(k) which is kth fibonacci number

which is greater than or equal to the size of array (n).
• Step 2: If F(k) = 0, then we need to stop here and print the message
as element not found.
• Step 3: Set variable offset = -1.
• Step 4: We need to set i = min( offset + F(k-2), n-1)
• Step 5: We will check:
• If search element (s) == Array[i] then, return i and stop the search.
• If search element (s) > Array[i] then, k = k-1, offset = i and we need to
repeat steps 4,5.
• If search element (s) < Array[i] then, k = k-2 repeat steps 4,5.
 i 0 1 2 3 4 5 6 7 8 9 10 11
A[i 3 4 6 8 10 14 16 18 20 34 56 67
]
Fib Fibm Fibm
Step 1: find F(k) which is kth fibonacci number which is
greater than or equal to the size of array (n).
1 2

F(n+1)=F(n)
+F(n-1)
 i 0 1 2 3 4 5 6 7 8 9 10 11
A[i 3 4 6 8 10 14 16 18 20 34 56 67
Search]Element x : 16

i = min( offset + fibm2,

n-1)

A[i] < x: A[i] > x:

A[i] == x fib = fibm1 fib = fibm2
return i fibm1 = fibm2 fibm1 = fibm1 -
fibm2 = fib - fibm2
fibm1 fibm2 = fib - fibm1
offset = i
 i 0 1 2 3 4 5 6 7 8 9 10 11
A[i 3 4 6 8 10 14 16 18 20 34 56 67
]
Search Element:
16
i = min( offset + Fibm2, n-1)
Offs Fib Fib1 Fib2
et
 i 0 1 2 3 4 5 6 7 8 9 10 11
A[i 3 4 6 8 10 14 16 18 20 34 56 67
]
Search Element:
16
i = min( offset + Fibm2, n-1)
Offs Fib Fib1 Fib2
et
def fibMonaccianSearch(arr, x, n):
# Initialize fibonacci numbers # If x is less than the value at
fibm2 = 0 # (m-2)'th Fibonacci # index fibMm2, cut the subarray
No. # after i+1
fibm1 = 1 # (m-1)'th Fibonacci
No. elif (arr[i] > x):
fib = fibm2 + fibm1 # m'th fib = fibm2
Fibonacci fibm1 = fibm1 - fibm2
fibm2 = fib - fibm1
while (fibM < n):
# element found. return index
fibm2 = fibm1
while (fib
fibm1> 1):
= fib else:
fib = fibm2 + fibm1 return i
offset# =Check
-1 if fibMm2 is a valid
location
i = min(offset+fibm2, n-1) # comparing the last element with x */
if(fibm1 and arr[n-1] == x):
# If x is greater than the value at return n-1
# index fibMm2, cut the subarray array from
offset to i
if (arr[i] < x): # element not found. return -1
fib = fibm1 return -1
fibm1 = fibm2
fibm2 = fib - fibm1
offset = i
# Driver Code
arr = [10, 22, 35, 40, 45, 50,80, 82, 85, 90, 100,235]
n = len(arr)
x = 235
ind = fibMonaccianSearch(arr, x, n)
if ind>=0:
print("Found at index:",ind)
else:
print(x,"isn't present in the array");
SELECTION SORT
• SELECTION SORT is a comparison sorting algorithm that is used to
sort a random list of items in ascending order.
• The comparison does not require a lot of extra space. It only requires
one extra memory space for the temporal variable.
• This is known as in-place sorting.
• The selection sort has a time complexity of O(n2) where n is the total
number of items in the list.
• The time complexity measures the number of iterations required to
sort the list.
SELECTION SORT

• The list is divided into two partitions: The first list

contains sorted items, while the second list contains
unsorted items

Sorted List Unsorted List

Algorithm
• Step 1) Get the value of n which is the total size of the array

• Step 2) Partition the list into sorted and unsorted sections.

• The sorted section is initially empty while the unsorted section contains the
entire list

• Step 3) Pick the minimum value from the unpartitioned section and
placed it into the sorted section.

• Step 4) Repeat the process (n – 1) times until all of the elements in

the list have been sorted.
 Example 1 4 9 5 3 6 2 1

Iteration 0

4 9 5 3 6 2 1 Iteration 4

Iteration 1 1 2 3 4 6 9 5
1 9 5 3 6 2 4
Iteration 5

Iteration 2 1 2 3 4 5 9 6
1 2 5 3 6 9 4
Iteration 6
Iteration 3
1 2 3 4 5 6 9
1 2 3 5 6 9 4
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
if array[i] < array[min_idx]:
min_idx = i # put min at the correct
position (array[step], array[min_idx]) = (array[min_idx],
array[step]) data = [-2, 45, 0, 11, -9] size = len(data)
selectionSort(data, size) print('Sorted Array in Ascending
Order:') print(data)
def selectionSort(array, size): Selection sort in
for step in range(size): Python
min_idx = step

for i in range(step + 1, size):

if array[i] < array[min_idx]:
min_idx = i

(array[step], array[min_idx]) = (array[min_idx],

array[step])

data = [-2, 45, 0, 11, -9]

size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)