การค้นหาแบบทวิภาค

ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (อังกฤษ: binary search, half-interval search หรือ bisection search) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าที่ต้องการ (ข้อมูลนำเข้า หรือ "key") ที่ใช้ในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว[1][2] ขั้นตอนวิธีจะเริ่มจากเปรียบเทียบข้อมูลที่นำเข้ากับข้อมูลที่อยู่ตรงกลางของแถวลำดับ ถ้าข้อมูลมีค่าเท่ากันแสดงว่าพบ "คีย์" ที่ต้องการ อาจจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าของข้อมูลนำเข้าที่ต้องการค้นหามีการน้อยกว่าค่าตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยของแถวลำดับที่ต้องการค้นหาโดยแถวลำดับย่อยจะมีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าข้อมูลที่ต้องการค้นหามีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก เมื่อทำไปจนแถวลำดับไม่มีสมาชิกอยู่หรือจุดเริ่มต้นมากกว่าจุดสิ้นสุด แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับข้อมูลนำเข้าที่ต้องการค้นหา อาจจะคืนค่าว่า "ไม่พบ"การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นหา

การค้นหาแบบทวิภาค

ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด O ( 1 ) {\displaystyle O(1)}
ประเภท ขั้นตอนวิธีการค้นหา
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป O ( log ⁡ n ) {\displaystyle O(\log n)}
โครงสร้างข้อมูล แถวลำดับ
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด O ( 1 ) {\displaystyle O(1)}
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด O ( log ⁡ n ) {\displaystyle O(\log n)}

ใกล้เคียง

การค้าประเวณี การค้าประเวณีเด็ก การค้นหาแบบทวิภาค การค้าประเวณีในประเทศไทย การค้าเครื่องเทศ การค้นหาแบบเอสตาร์ การค้าระหว่างประเทศ การค้นหาและกู้ภัยในเขตเมือง การค้นหาในแนวกว้าง การค้นหาในแนวลึกแบบวนเพิ่มความลึก