Data Structure and
Algorithm (CS 102)
Ashok K Turuk
Searching
Finding the location of an given item in a
collection of item
Linear Search with Array
2
12
Algorithm
[1] i = 1
[2] If K = A[i] , Print Search is
Successful and Stop
[3] i = i + 1
[4] If (i <= n) then Go To Step [2]
[5] Else Print Search is
Unsuccessful and Stop
[6] Exit
Complexity Of Linear Search Array
Case 1: Key matches with the first
element
T(n) = Number of Comparison
T(n) = 1, Best Case = O(1)
Case 2: Key does not exist
T(n) = n, Worst Case = O(n)
Case 3: Key is present at any location
T(n) = (n+1)/2, Average Case = O(n)
Linear Search with Linked List
A
Head
Best Case
Worst Case
Average Case
Linear Search with Ordered List
5
10
13
56
76
82
110
112
10
Algorithm
[1] i = 1
[2] If K = A[i] , Print Search is
Successful and Stop
[3] i = i + 1
[4] If (i <= n) and (A[i] <= K) then Go To
Step [2]
[5] Else Print Search is
Unsuccessful and Stop
[6] Exit
Complexity
Case 1: Key matches with the first
element
T(n) = Number of Comparison
T(n) = 1, Best Case = O(1)
Case 2: Key does not exist
T(n) = (n + 1)/2, Worst Case = O(n)
Case 3: Key is present at any location
T(n) = (n+1)/2, Average Case = O(n)
Binary Search
l
l
If K < A[mid]
mid
u
mid = (l + u) /2 K = A[mid] then done
u
mid
u = mid -1
mid l
If K > A[mid] l = mid +1
Algorithm
[1] l =1, u =n
[2] while (l < u) repeat steps 3 to 7
[3] mid = (l + u) / 2
[4] if K = A[mid] then print Successful and
Stop
[5] if K < A[mid] then
[6] u = mid -1
[7] else l = mid + 1
[8] Print Unsuccessful and Exit
Example
1
15
25
35
45
65
75
85
95
l
1
u
8
15
25
35
45
65
75
85
95
l=4+1
15
25
35
45
65
75
85
95
l=4+1
K = 75
l=1
u =8
l=1
u =8
mid = 4
K = 75 > A[4]
l=5
u =8
mid = 6
K = 75 = A[6]
Example
1
15
25
35
45
65
75
85
95
l
1
u
8
15
25
35
45
65
75
85
95
l=4+1
15
25
35
45
65
75
85
95
l=4+1
u= 6-1
K = 55
l=1
u =8
l=1
u =8
mid = 4
K = 55 > A[4]
l=5
u =8
mid = 6
K = 55 < A[6]
15
25
35
45
65 75
l=5
u= 5-1
85
95
l=5
u =8
mid = 5
K = 55 < A[5]
Fibonacci Search
Fn = F n 1 + F n 2
with F0 = 0 and F1 = 1
If we expand the nth Fibonacci number
into the form of a recurrence tree, its
result into a binary tree and we can
term this as Fibonacci tree of order n.
In a Fibonacci tree, a node correspond to
Fi the ith Fibonacci number
Fi-1 is the left subtree
Fi-2 is the right subtree
Fi-1 and Fi-2 are further expanded until F0
and F1.
Fibonacci Tree
F6
Fc5
Fc4
Fc3
F2c
Fc1
Fc
Fc3
F2c
Fc0
Fc4
Fc1
Fc2
Fc1
Fc0
Fc 3
Fc1
c
Fc 2 F1
Fc2
Fc0
Fc1
Fc2
Fc0
A Fibonacci Tree of Order 6
Fc0
Apply the following two rules to obtain
the Fibonacci search tree of order n
from a Fibonacci tree of order n
Rule 1: For all leaf nodes corresponding to
F1 and F0, we denote them as external
nodes and redraw them as squares, and
the value of each external node is set to
zero. Value of each node is replaced by
its corresponding Fibonacci number.
Rule 2: For all nodes corresponding to F i
(i>=2), each of them as a Fibonacci
search tree of order i such that
(a) the root is Fi
(b) the left-subtree is a Fibonacci
search tree of order i -1
(c) the right-subtree is a Fibonacci
search tree of order i -2 with all
numbers increased by Fi
Fibonacci Tree
F6
Fc5
Fc4
Fc3
F2c
0
0
0
Fc4
Fc3
F2c
0
Fc2
0
0
Fc2
Fc 3
Fc2
0
0
0
0
Rule 1 applied to Fibonacci Tree
of Order 6
Fibonacci Tree
8
5c
c
3
2c
1c
0
0
0
c3
c
2
1c
0
1c
0
0
1c
2c
c1
0
0
0
0
Rule 1 applied to Fibonacci Tree
of Order 6
Fibonacci Tree
8
5c
c
3
2c
1c
0
2
1
11
c
c
7
4c
3
6c
5
4
12
c
c
10
10
c9
6
8
12
11
Rule 2 applied to Fibonacci Tree
of Order 6
Algorithm
Elements are in sorted order. Number of
elements n is related to a perfect
Fibonacci number Fk+1 such that Fk+1 =
n+1
[1] i = Fk
[2] p = Fk-1 , q = Fk-2
[3] If ( K < Ki ) then
[4] If (q==0) then Print unsuccessful
and exit
[5]
Else i = i q, pold = p, p =q,
q =pold q
[6] Goto step 3
[7] If (K > Ki ) then
[8] If (p ==1) then Print Unsuccessful
and Exit
[9] Else i = i + q, pold=p, p = p+q,
q=pold
[10] Goto step 3
[11] If ( k == Ki ) then Print Successful at
ith location
[12] Stop
Example
1
10
11
12
15
20
25
30
35
40
45
50
65
75
85
95
K = 25
Initialization: i = Fk = 8, p = Fk-1 = 5, q = Fk-2 = 3
Iteration 1;
K8 = A[8] = 50, K < K8 , q == 3
i = i q = 8 -3 = 5, pold = p =5
p=q= 3, q = pold q = 5-3 = 2
Iteration 2;
K5 = A[5] = 35, K < K5 , q == 2
i = i q = 5 -2 = 3, pold = p =3
p=q= 2, q = pold q = 3-2 = 1
10
11
12
15
20
25
30
35
40
45
50
65
75
85
95
Iteration 2;
K3 = A[3] = 25,
K = K3
Search is successful