What letters are interrogated by the binary search (Figure 5.14) if it is applie

Question

What letters are interrogated by the binary search (Figure 5.14) if it is applied to the list A, B, C, D, E, F, G, H, I, J, K, L, ?, N, O when searching for the value J? What about searching for the value Z? Binary search algorithm procedure Search (List, TargetValue) if (List empty) then (Report that the search failed.) else [Select the "m id d le " entry in List to be the TestEntry; Execute the block of instructions below that is associated with the appropriate case, case 1: TargetValue = TestEntry (Report that the search succeeded.) case 2: TargetValue TestEntry (Apply the procedure Search to see if TargetValue is in the portion of List following TestEntry, and report the result of that search.) ] end if

Explanation / Answer

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

A B C D E F G H I J   K   L   M  N O

Middle = (1+15)/2 = 8

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

A B C D E F G H I J   K  L   M   N O

Here J > H

So middle = (8+15) /2 = 23/2 = 11

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

A B C D E F G H I J   K  L   M   N O

Here j < K

So middle = (8 + 11) /2 = 9

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

A B C D E F G H I J   K  L   M   N O

At 9 it is I

Here J > i

Middle = 10 + 11 / 2 =10

At 10 it is J , so found

So letter interrogated are :

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

A B C D E F G H I J   K  L   M   N O

Middle = (1+15)/2 = 8

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

A B C D E F G H I J   K  L   M   N O

Here Z > H

So middle = (8+15) /2 = 23/2 = 11

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

A B C D E F G H I J   K   L  M   N O

HereZ > K

So middle = (11 + 15) /2 = 13

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

A B C D E F G H I J   K   L   M  N O

Here Z > M

So middle = (13 + 15) /2 = 14

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

A B C D E F G H I J   K   L   M  N O

Here Z > N

So middle = (11 + 15) /2 = 13

Now list is empty , so not found

So letter interrogated are :

H, K , M,N

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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