ลิสต์ที่เรียงจากน้อยไปมากมีสมาชิก 15 ตัว คือ [3, 7, 10, 14, 18, 21,…

ลิสต์ที่เรียงจากน้อยไปมากมีสมาชิก 15 ตัว คือ [3, 7, 10, 14, 18, 21, 25, 30, 33, 38, 41, 45, 50, 56, 60] หากค้นหาค่า 45 ด้วยการค้นหาแบบทวิภาค (binary search) โดยใช้ดัชนีเริ่มที่ 0 และเลือกตำแหน่งกลาง mid = (low + high) // 2 ต้องเปรียบเทียบกับสมาชิกในลิสต์กี่ครั้งจึงพบ

• ก.4 ครั้ง
• ข.12 ครั้ง
• ค.2 ครั้ง
• ง.3 ครั้ง

ดูเฉลยและคำอธิบาย

คำตอบ: ค. 2 ครั้ง

รอบแรก low = 0, high = 14 ได้ mid = 7 ค่า 30 น้อยกว่า 45 จึงเลื่อน low = 8 · รอบสอง mid = (8 + 14) // 2 = 11 ค่า 45 ตรงกับที่ค้นหา รวม 2 ครั้ง

12 ครั้งเป็นจำนวนของการค้นหาแบบลำดับที่ไล่จากตัวแรกถึงดัชนี 11 · 4 ครั้งเป็นจำนวนสูงสุดที่อาจต้องใช้กับข้อมูล 15 ตัว ไม่ใช่กรณีของค่า 45 · 3 ครั้งเกิดจากนับรอบผิด

ประเด็นของข้อนี้: การค้นหาแบบทวิภาค

ตรวจเทียบแหล่ง ณ 13 ต.ค. 2569 · หมวด: ครูผู้ช่วย วิชาเอกคอมพิวเตอร์