4.41

Binary search (arrays kept sorted)
Single array:  n = 10 000 ⇒ cost ≃ ⌈log₂10 000⌉ = 14 comparisons.
Two–array scheme:
  • “good’’ array n₁ = 4 000 ⇒ c₁ = ⌈log₂4 000⌉ = 12
  • “other’’ array n₂ = 6 000 ⇒ c₂ = ⌈log₂6 000⌉ = 13
Expected comparisons
[math]E = 0.6·c_1 + 0.4·(c_1+c_2) = 0.6·12 + 0.4·25 = 17.2.[/math]
Since 17.2 > 14, the single sorted array is the faster choice when binary search is used.

Linear (sequential) search on unsorted arrays
For an array of length n: average successful cost = (n+1)/2, unsuccessful cost = n.
Single array (n = 10 000):
[math]E = (10 000+1)/2 = 5\,000.5.[/math]
Two–array scheme:
  • Hit in “good’’ set (60 %): (4 000+1)/2 = 2 000.5
  • Hit in “other’’ set (40 %): 4 000 (miss in first) + (6 000+1)/2 = 7 000.5
[math]E = 0.6·2\,000.5 + 0.4·7\,000.5 = 4\,000.5.[/math]
Here 4 000.5 < 5 000.5, so the split-array organisation wins when only linear search is available.

Conclusion
• With binary search keep a single sorted array (≈14 comparisons/query).
• With linear search divide the customers; the expected cost drops by ≈20 % (5 000.5 → 4 000.5).

Back to Chapter 4