Binary Search
เราเขียน binary search ได้หลายแบบ เขียนได้ทั้งแบบ recursive และเขียนแบบวงวน นอกจากนี้ ยังเลือกลำดับการเปรียบเทียบในหลายแบบด้วย โดยทั่วไปเรามักเปรียบเทียบว่าตรงหรือเปล่าก่อน เพราะจะได้รีบ ๆ ดีใจว่าค้นแล้วพบ แต่ลองคิดสิว่า การค้นข้อมูลในอาเรย์หนึ่งล้านตัว ก็มีเพียงหนึ่งในล้านเท่านั้น ที่จะเปรียบเทียบแล้วตรง นี่ยังไม่รวมกรณีที่ค้นข้อมูลทั่วไปที่มีโอกาสไม่พบ ดังนั้นควรจะเปรียบเทียบกรณีน้อยกว่ามากกว่าเสียก่อน จะได้รีบ ๆ ตัดสินใจค้นต่อทางซ้ายหรือทางขวา (ปล่อยกรณีว่าค้นพบไว้เป็นกรณีสุดท้าย)
นอกจากนี้เราอาจไม่สนใจกรณีเปรียบเทียบแล้วเท่าเลย คิดแต่จะไปทางซ้ายหรือทางขวา คือกรณีมากกว่ากับกรณีน้อยกว่าหรือเท่ากับ เมื่อค้นจนเหลือตัวเดียว ค่อยเปรียบเทียบว่าเท่าหรือไม่ แต่ละรอบที่ทำงานจึงเปรียบเทียบแค่ครั้งเดียว ลองดูสิว่าทั้งสามแบบ มีประสิทธิภาพการทำงานอย่างไร และเปรียบเทียบดูสิว่า เขียนแบบ recursive กับแบบวงวนต่างกันอย่างไร
(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)
Binary Search (แบบ recursive)
การทดลองข้างล่างนี้ ค้นข้อมูลที่มีอยู่ในอาเรย์ทุกตัว ตัวละครั้ง สะสมการนับจำนวนครั้งของการทำงาน
การทดลองข้างล่างนี้ ค้นข้อมูลที่ไม่มีอยู่ในอาเรย์ โดยเลือกค้นตัวที่ไม่มีที่อยู่ระหว่างข้อมูลที่มีในอาเรย์ สะสมการนับจำนวนครั้งของการทำงาน
Binary Search (แบบวงวน)
การทดลองข้างล่างนี้ ค้นข้อมูลที่มีอยู่ในอาเรย์ทุกตัว ตัวละครั้ง สะสมการนับจำนวนครั้งของการทำงาน
การทดลองข้างล่างนี้ ค้นข้อมูลที่ไม่มีอยู่ในอาเรย์ โดยเลือกค้นตัวที่ไม่มีที่อยู่ระหว่างข้อมูลที่มีในอาเรย์ สะสมการนับจำนวนครั้งของการทำงาน
สมชาย ประสิทธิ์จูตระกูล