ตอนท้ายของบล็อกเรื่องโยนไข่ มีพูดถึงอัลกอริทึม binary search ซึ่งแปะลิงค์ไปที่นี่ และบอกว่าเป็นอัลกอริทึมที่ดีที่สุด

บล็อกนี้จะอธิบายเป็นภาษาไทยง่ายๆว่าจะพิสูจน์ได้ยังไงว่ามันดีที่สุดจริงๆ โดยใช้ analogy เป็นปัญหาโยนไข่เหมือนบล็อกก่อนๆ

แนวคิดคือให้ลองตอบคำถามต่อไปนี้

• คำตอบที่เป็นไปได้ของโจทย์มีกี่แบบ
  • มี N แบบ
  • นั่นคือ “ไข่จะแตกเมื่อโยนจากความสูงตั้งแต่ชั้นที่ i เป็นต้นไป” โดยที่ $ 1 \le i \le N $
• การทดลองโยนไข่หนึ่งครั้งมีผลลัพธ์ที่เป็นไปได้กี่แบบ
  • ผลลัพธ์ที่เป็นไปได้จะมี 2 แบบคือ แตกหรือไม่แตก
• การทดลองโยนไข่ k ครั้ง มีผลลัพธ์ที่เป็นไปได้กี่แบบ
  • คำตอบคือ $ 2^k $ แบบ

แปลว่าถ้าเราสร้าง function

$ f(result) = answer $

จากผลลัพธ์การโยนที่เป็นไปได้ (result) ไปยังคำตอบของปัญหา (answer)

การที่เราจะสามารถครอบคลุมคำตอบที่เป็นไปได้ทั้งหมด เราก็ต้องมีจำนวนผลลัพธ์ไม่น้อยไปกว่าจำนวนคำตอบที่เป็นไปได้

เพราะถ้าหากอัลกอริทึม A มีจำนวนผลลัพธ์การโยนน้อยกว่าแล้ว จะมีบางคำตอบ i ที่ A ไม่มีทางตอบ ซึ่งเราสามารถสร้างข้อมูลนำเข้าที่มีคำตอบเป็น i ทำให้อัลกอริทึม A ผิดได้เสมอ

เพราะฉะนั้นเพื่อสร้างจำนวนผลลัพธ์ให้ครอบคลุมคำตอบ เราจะได้ว่า

\[\begin{align} 2^k &\ge N \\ k &\ge log_2 N \end{align}\]

นั่นคือต้องโยนอย่างน้อย $ O(log N) $ ครั้ง