Data Structures and Algorithms - Old Questions
8. Trace Binary Search algorithm for the data:
21, 36, 56, 79, 101, 123, 142, 203
And Search for the values 123 and 153.
5 marks
|
Asked in 2066
Given:
21, 36, 56, 79, 101, 123, 142, 203
Now,
Tracing binary search for given data;
Set L=0, R=7, key=123 (search for 123)
|
S.No. |
L |
R |
Mid=(L+R)/2 |
Remarks |
|
1. 2. |
0 4 |
7 7 |
(0+7)/2=3 (4+7)/2=5 |
Key>a[3] Key==a[5] |
Therefore, search successful and key(123)
is at position (Mid+1)=5+1=6.
Again,
L=0, R=14, key=153 (search for 153)
|
S.No. |
L |
R |
Mid=(L+R)/2 |
Remarks |
|
1. 2. 3. 4. 5. |
0 4 6 7 7 |
7 7 7 7 6 |
(0+7)/2=3 (4+7)/2=5 (6+7)/3=6 (7+7)/2=7 - |
Key>a[3] Key>a[5] Key>a[6] Key<a[7] L>R |
Therefore, search failure and key(153) is not present in the given list.