Answer:
4, 8 and 12
Explanation:
Given
[tex]Array: 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 14\ 15[/tex]
[tex]n = 15[/tex]
Required
Elements that would be found by examining 2 or fewer numbers
To do this, we apply the following binary search algorithm
[tex]head = 1[/tex] at 0-index
[tex]tail = 15[/tex] at 14-index
Calculate the mid-index
[tex]Mid = \frac{0 + 14}{2}[/tex]
[tex]Mid = \frac{14}{2}[/tex]
[tex]Mid = 7th[/tex]
The mid-element (at 7th index) is:
[tex]Mid = 8[/tex]
The element at the mid-index is found by just 1 comparison
For 2 comparisons, we search in either directions
For the lower half, the new head and tail are:
[tex]head = 1[/tex] ---- at 0-index
[tex]tail = 7[/tex] at 6-index
Calculate the mid-index
[tex]Mid = \frac{0 + 6}{2}[/tex]
[tex]Mid = \frac{6}{2}[/tex]
[tex]Mid = 3rd[/tex]
The mid-element (at 3rd index) is:
[tex]Mid = 4[/tex]
For the upper half, the new head and tail are:
[tex]head = 9[/tex] ---- at 8-index
[tex]tail = 15[/tex] at 14-index
Calculate the mid-index
[tex]Mid = \frac{8 + 14}{2}[/tex]
[tex]Mid = \frac{22}{2}[/tex]
[tex]Mid = 11th[/tex]
The mid-element (at 11th index) is:
[tex]Mid = 12[/tex]
The elements at the mid-index of both halves is found by 2 comparisons
Hence, the numbers are: [tex]4, 8, 12[/tex]
