Answer:
3 comparisons
Step-by-step explanation:
Given:
[tex]List: 1 , 5 ,10 , 13 , 48 , 68 , 100 , 101[/tex]
Required
Determine the number of comparisons to get to 101
The length of the list is 8. So, the first index is 0 and the last is 7.
We have:
[tex]List[0] = 1[/tex] [tex]List[1] = 5[/tex] [tex]List[2] = 10[/tex] [tex]List[3] = 13[/tex]
[tex]List[4] = 48[/tex] [tex]List[5] = 68[/tex] [tex]List[6] = 100[/tex] [tex]List[7] = 101[/tex]
Initially:
[tex]begin = 0[/tex] -- first index
[tex]end = 7[/tex] --- last index
Start by calculating the mid-item
[tex]mid = \frac{1}{2}(begin + end)[/tex]
[tex]mid = \frac{1}{2}(0 + 7)[/tex]
[tex]mid = \frac{1}{2}(7)[/tex]
[tex]mid = 3.5[/tex]
[tex]mid = 4[/tex] --- approximated.
The mid-index is 4 and the item is:
[tex]List[4] = 48[/tex]
101 is on the right of 48.
So, we calculate the new begin index.
[tex]begin = mid + 1[/tex]
[tex]begin= 4 +1[/tex]
[tex]begin = 5[/tex]
Calculate mid
[tex]mid = \frac{1}{2}(begin + end)[/tex]
[tex]mid = \frac{1}{2}(5 + 7)[/tex]
[tex]mid = \frac{1}{2}(12)[/tex]
[tex]mid= 6[/tex]
The mid-index is 6 and the item is:
[tex]List[6] = 100[/tex]
101 is on the right of 100.
So, we calculate the new begin index.
[tex]begin = mid + 1[/tex]
[tex]begin = 6 +1[/tex]
[tex]begin= 7[/tex]
Calculate mid
[tex]mid = \frac{1}{2}(begin + end)[/tex]
[tex]mid = \frac{1}{2}(7+7)[/tex]
[tex]mid = \frac{1}{2}(14)[/tex]
[tex]mid = 7[/tex]
At this point, the mid-index is at 101
i.e.
[tex]List[7] = 101[/tex]
This implies that, we have located 101.
So far, we made 3 comparisons
[tex]4[/tex] comparisons are needed to find the number [tex]101[/tex] in the list.
Binary search algorithm searches for a number in a sorted list/array. It does this by first comparing the number in the middle of the array with the number searched for, then recursively continuing the search on either the left-half or right-half of the array if the middle comparison failed.
The element [tex]101[/tex], is at the rightmost end of the array. This means that the algorithm will have a worst case running time. The worst case running time of a binary search algorithm is given by
[tex]T_n=\lfloor log_2(n)+1\rfloor[/tex]
where [tex]\lfloor x \rfloor[/tex] is the floor function that gives the greatest integer less than or equal to [tex]x[/tex], and [tex]log_2(n)[/tex] is the logarithm of [tex]n[/tex] to base [tex]2[/tex]
In our case, the number of elements in the array, [tex]n=8[/tex]. So,
[tex]T_n=\lfloor log_2(n)+1\rfloor\\\implies T_8=\lfloor log_2(8)+1\rfloor = 4\\[/tex]
So, the algorithm will need to make [tex]4[/tex] mid-array comparisons to get to [tex]101[/tex].
Learn more about Binary search here: https://brainly.com/question/11305694
