MCQ IN COMPUTER SCIENCE & ENGINEERING

Previous
Next

COMPUTER SCIENCE AND ENGINEERING

ALGORITHMS

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
A computer is performing a binary search on the sorted list of 7 numbers below. What is the maximum number of iterations needed to find the item?[1, 5, 20, 50, 51, 80, 99]
A
1
B
3
C
6
D
7
Explanation: 

Detailed explanation-1: -Thus, the number of iterations needed to find the item is 3 iterations.

Detailed explanation-2: -The maximum number of iterations or invocations would thus be 10 for a data set of 1024 items, for example, because the logarithm to the base of two of 1024 is 10. The worst case scenario for a linear search would be 1024 for the same data set.

Detailed explanation-3: -Mathematically Maximum iteration possible (Assuming case of only integer type) is = ceil( log2 ( initial r-initial l ) ) base of log is 2 because every time we are diving our range in half by taking a mid and switching to one of the half.

Detailed explanation-4: -The number of comparisons necessary to get to this point is i where n2i=1. Solving for i gives us i=logn. The maximum number of comparisons is logarithmic with respect to the number of items in the list. Therefore, the binary search is O(logn).

Detailed explanation-5: -It examines up to log2(n) elements.

There is 1 question to complete.
Previous
Next