Question

A) Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Suppose that we are doing a binary search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.

Answer 1

4, 8 and 12

Step-by-step explanation:

Given

`Array: 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 14\ 15`

`n = 15`

Required

Elements that would be found by examining 2 or fewer numbers

To do this, we apply the following binary search algorithm

`head = 1` at 0-index

`tail = 15` at 14-index

Calculate the mid-index

`Mid = (0 + 14)/(2)`

`Mid = (14)/(2)`

`Mid = 7th`

The mid-element (at 7th index) is:

`Mid = 8`

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:

`head = 1` ---- at 0-index

`tail = 7` at 6-index

Calculate the mid-index

`Mid = (0 + 6)/(2)`

`Mid = (6)/(2)`

`Mid = 3rd`

The mid-element (at 3rd index) is:

`Mid = 4`

For the upper half, the new head and tail are:

`head = 9` ---- at 8-index

`tail = 15` at 14-index

Calculate the mid-index

`Mid = (8 + 14)/(2)`

`Mid = (22)/(2)`

`Mid = 11th`

The mid-element (at 11th index) is:

`Mid = 12`

The elements at the mid-index of both halves is found by 2 comparisons

Hence, the numbers are:
`4, 8, 12`