Answer:
The indexes of the elements that would be examined by the binary search are
7 11 9
numbers[7] = 39
numbers[11] = 57
numbers[9] = 42
The values that would be returned from the search are
39 57 42
Explanation:
The complexity of searching a value in an array using binary search is O (log n). It follows divide and conquer principle. First we have to sort the elements in the array. Here in our case the array is already sorted.
target = (search for the value) =42
numbers[] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
min max
here assign min= 0 (minimum index)
max= 14 (maximum index)
Instead of searching for the target in a sequential manner we are searching by examining the middle term in the array by using the following formula. middle = ( min + max )/2
step 1) middle = (0 + 14)/2 = 7 numbers[middle]=numbers[7] = 39
compare target value with numbers[middle]
i.e target = 42 > 39 , the target value is greater than the numbers[middle]. so we have to move to upper part of the array.
Then min= middle+1 = 7+1 = 8
max= (unchanged) 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
min max
step 2) middle = (8+ 14)/2 = 11 numbers[middle]=numbers[11] = 57
compare target value with numbers[middle]
i.e target = 42 < 57 ,the target value is lesser than the numbers[middle] .
Then min= (unchanged) 8
max= middle -1 =11-1 =10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
min max
step 3) middle = (8+10)/2 = 9 numbers[middle]=numbers[9] = 42
i.e target = 42 = 42
Here stop the process. In this way we found our target using binary search.
