2. Suppose we are performing a binary search on a sorted array called numbers in

Question

2. Suppose we are performing a binary search on a sorted array called numbers initialized as follows:
// index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
int[] numbers = {-5, -1, 0, 3, 9, 14, 19, 24, 33, 41, 56, 62, 70, 88, 99};
int index = binarySearch(numbers, 37);
Write the indexes of the elements that would be examined by the binary search (the mid values in our
algorithm's code) and write the value that would be returned from the search. Assume that we are using
the binary search algorithm we discussed in our class. (7 points)
Indexes examined: ___________________________________________________________
Value Returned: __________________________

Explanation / Answer

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

int[] numbers = {-5, -1, 0, 3, 9, 14, 19, 24, 33, 41, 56, 62, 70, 88, 99};

int index = binarySearch(numbers, 37);

THe index number looks like this

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

{-5, -1, 0, 3, 9, 14, 19, 24, 33, 41, 56, 62, 70, 88, 99}

mid = (high + low) / 2

= (14+0)/2

= 7

so the middle value is 24

As the search value 37 greater than 24 we will go to the upper portion of the array

8 9 10 11 12 13 14

33, 41, 56, 62, 70, 88, 99

low=mid+1=8

mid = (high + low) / 2

= (14+8)/2

= 11

so the middle value is 62

As the search value 37 lesser than 24 we will go to the lower portion of the array

8 9 10

33, 41, 56

low=8

high=mid-1

=11-1=10

mid = (high + low) / 2

= (10+8)/2

= 9

so the middle value is 41

As the search value 37 lesser than 24 we will go to the lower portion of the array

8   

33

low=8

high=9-1

=9-1=8

mid = (high + low) / 2

= (8+8)/2

= 8

so the middle value is 33

But the search value is 37 so the number is not present

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

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