Consider the following list. list = {5, 11, 25, 28, 45, 78, 100, 120, 125}; Supp

Question

Consider the following list.

list = {5, 11, 25, 28, 45, 78, 100, 120, 125};

Suppose that binary search as discussed in the book is used to determine whether 110 is in list. Exactly how many key comparisons are executed by binary search?

A) 3

B) 5

C) 8

D) 12

I selected D) 12 and it was the incorrect answer.

Consider the following list.

list = {5, 11, 25, 28, 45, 78, 100, 120, 125};

Suppose that binary search as discussed in the book is used to determine whether 110 is in list. Exactly how many key comparisons are executed by binary search?

A) 3

B) 5

C) 8

D) 12

I selected D) 12 and it was the incorrect answer.

Explanation / Answer

In a sorted array, binary search acts by comparing the item being searched to the item in the middle of the list to determine whether the item will occur in the upper or lower half of the list. This continues till the item is found or there is no more item to search.

In our case,

list = {5, 11, 25, 28, 45, 78, 100, 120, 125};

Iteration 1:

Low=5

High=125

Middle item=45

Searched item=110

Since searched item>middle term, the item would be searched in the upper half.

Target list={ 78, 100, 120, 125}

Iteration 2:

Target list={ 78, 100, 120, 125}

Since the number of elements is even, the midpoint is calculated by integer division.

Mid point=100

Search item=110

Search Item>Mid point

Target list={120,125}

Lower bound=120

Upper bound=125

Therefore, number of iterations required for the given search would be 3.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.