Q.For L = [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]. Fill up the Table 6.8 for the given key values 2, 43, 17 and 9. What do you infer from Table 6.8 regarding performance of both the algorithms in different cases?
[Table: the referenced comparison-table template could not be located in this reprint — the only printed Table 6.8 is the unrelated empty hash table in Section 6.4.]
You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.
Start your 14-day free trial to unlock the full solution →For L = [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43], filling Table 6.8 gives — linear search: 1, 15, 8, 15 comparisons for the keys 2, 43, 17, 9; binary search: 4, 4, 1, 4. The inference is that binary search is consistently efficient (never more than about comparisons), while linear search is fast only when the key sits near the start and degrades to scanning the whole list when the key is at the end or absent.
Setting up the count
The list has 15 elements and is already sorted, which is what lets binary search apply:
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
value: 2 3 5 7 10 11 12 17 19 23 29 31 37 41 43
We count one comparison each time an algorithm tests a list element against the key.
Linear search — scan from the front
Linear search checks L[0], then L[1], and so on until it finds the key or runs off the end.
- Key 2 is
L[0]→ found on the 1st comparison. - Key 43 is
L[14], the last element → the scan tests all 15 → 15 comparisons. - Key 17 is
L[7]→ found on the 8th comparison. - Key 9 is not in the list → the scan tests all 15 elements before concluding it is absent → 15 comparisons.
Binary search — halve the range each step
Binary search looks at the middle element, then discards the half that cannot contain the key.
- Key 2: mid
L[7]=17(2<17, go left) →L[3]=7(2<7, left) →L[1]=3(2<3, left) →L[0]=2found. 4 comparisons. - Key 43:
L[7]=17(43>17, right) →L[11]=31(43>31, right) →L[13]=41(43>41, right) →L[14]=43found. 4 comparisons. - Key 17:
L[7]=17found at once. 1 comparison. - Key 9:
L[7]=17(9<17, left) →L[3]=7(9>7, right) →L[5]=11(9<11, left) →L[4]=10(9<10, left) → range empty, absent. 4 comparisons.
Table 6.8 (filled)
| Key | Linear Search (comparisons) | Binary Search (comparisons) | Present? |
|---|---|---|---|
| 2 | 1 | 4 | yes — first element |
| 43 | 15 | 4 | yes — last element |
| 17 | 8 | 1 | yes — middle element |
| 9 | 15 | 4 | no |
What the table tells us
- Linear search makes as many comparisons as the position of the key. It is at its best when the key is at (or near) the start — key 2 costs just 1 comparison. It is at its worst when the key is at the end, or not present at all, because it must then examine every element (keys 43 and 9 → 15 comparisons). …
Unlock everything free for 14 days
- Full step-by-step solutions
- Concept-first explanations
- Methods, shortcuts & mistakes
- PYQ mapping + timed mock tests
Full access for 14 days. No credit card required.