Consider the following list: 2 10 17 45 49 55 68 85 92 98 110 Using a binary sea

Question

Consider the following list:
2 10 17 45 49 55 68 85 92 98 110

Using a binary search algorithm, how many comparisons are required to determine whether the following items are in the list or not? show the values of first, last, and middle and the number of comparisons after each iteration of the loop.

Iteration first last middle list[middle] no. of comparisons
a. 15 ______ ________ ______ _____
b. 49 ______ ________ _______ ______
c. 98 ______ _______ _______ _______
d. 99 ______ ________ ______ ______

Explanation / Answer

From my previous answer:

high would be the value of the last number.
low would be the value of the first number.
mid would be the value of thee middle number.

the number of comparisons would be the last iteration number.

Below is an updated list of outputs.
(Again the C/C++ source code is viewable at:
  http://codepad.org/wu0omuAL)

If you need more clarifications, please let me know on my profile before rating it so I can edit without having to submit a new answer.

{2, 10, 17, 45, 49, 55, 68, 85, 92, 98, 110}

searching for 15
--------------------
iteration #1 - first: 2, last: 110, middle: 55
iteration #2 - first: 2, last: 49, middle: 17
iteration #3 - first: 2, last: 10, middle: 2
iteration #4 - first: 10, last: 10, middle: 10
>> 15 was not found
>> number of comparisons: 4

searching for 49
--------------------
iteration #1 - first: 2, last: 110, middle: 55
iteration #2 - first: 2, last: 49, middle: 17
iteration #3 - first: 45, last: 49, middle: 45
iteration #4 - first: 49, last: 49, middle: 49
>> 49 was found
>> number of comparisons: 4

searching for 98
--------------------
iteration #1 - first: 2, last: 110, middle: 55
iteration #2 - first: 68, last: 110, middle: 92
iteration #3 - first: 98, last: 110, middle: 98
>> 98 was found
>> number of comparisons: 3

searching for 99
--------------------
iteration #1 - first: 2, last: 110, middle: 55
iteration #2 - first: 68, last: 110, middle: 92
iteration #3 - first: 98, last: 110, middle: 98
iteration #4 - first: 110, last: 110, middle: 110
>> 99 was not found
>> number of comparisons: 4

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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