1.

Work through Binary Search algorithm on an ordered file with the following keys: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}. Determine the number of key comparisons made while searching for keys 2, 10 and 15. 

Answer»

Here List={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

Binary Search for key 2  

(1) Here bottom =1 Top =16 and middle =(1+16)/2 = 8

Since 2 < list(8) 

(2) bottom = 1 Top = middle-1=7 and middle=(1+7)/2 =4

2 < list(4) 

(3) bottom = 1 Top = middle-1=3 and middle=(1+3)/2 = 2

2 = List(2)

So total number of comparisons require = 3

Binary Search for key = 10

(1) Here bottom=1 Top=16 and middle = 8

10 > List(8)

(2) bottom = middle+1=9 Top=16 middle=(9+16)/2=12 

10 < List(12)

(3) bottom =9 Top=middle-1=11 middle=(9+11)/2=10

10 = List(10)

So total no of comparisons = 3

Binary Search for key = 15 

(1) Here bottom=1 Top=16 and middle = 8

15 > List(8) 

(2) bottom = middle+1=9 Top=16 middle=(9+16)/2=12

15 > List(12) 

(3) bottom =middle+1=13 Top=16 middle=(13+16)/2=14

15 > List(14)

(4) bottom = middle+1 =15 Top=16 middle=(15+16)/2=15 

15=List(15)

So total no of comparisons = 4


Discussion

No Comment Found

Related InterviewSolutions