Binary Search — อัลกอริทึม ความซับซ้อนเชิงเวลา และโค้ด

Binary search เป็นวิธีที่รวดเร็วในการหาค่าเป้าหมายในลิสต์ที่เรียงลำดับแล้ว คุณตรวจดูค่าตรงกลาง ตัดค่าที่เหลือทิ้งไปครึ่งหนึ่ง แล้วทำซ้ำ ถ้าลิสต์ไม่ได้เรียงลำดับ ตรรกะนี้จะใช้ไม่ได้

สำหรับลิสต์ที่เรียงจากน้อยไปมาก กฎนั้นง่ายมาก: ถ้าค่าตรงกลางน้อยกว่าค่าเป้าหมาย ให้ค้นหาทางขวา ถ้ามากกว่า ให้ค้นหาทางซ้าย เพราะช่วงข้อมูลถูกลดลงประมาณครึ่งหนึ่งทุกครั้ง Binary search จึงใช้เวลา $O(\log n)$

Binary search ทำงานอย่างไรกับลิสต์ที่เรียงแล้ว

ใช้ลิสต์ที่เรียงแล้วนี้:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

สมมติว่าค่าเป้าหมายคือ $31$

เริ่มจากช่วงทั้งหมด ค่าตรงกลางคือ $24$ เนื่องจาก $31 > 24$ ทุกค่าทางซ้ายของ $24$ จึงตัดทิ้งได้ และการค้นหาจะดำเนินต่อในช่วง

$$[31, 39, 45, 52]$$

ตอนนี้ค่าตรงกลางคือ $39$ เนื่องจาก $31 < 39$ ทุกค่าทางขวาของ $39$ จึงตัดทิ้งได้ ทำให้ช่วงกลายเป็น

$$[31]$$

ตอนนี้ค่าตรงกลางคือ $31$ ดังนั้นการค้นหาจึงหยุด แนวคิดสำคัญไม่ได้มีแค่ว่าพบค่าเป้าหมายเท่านั้น แต่คือในเวลาเพียงสองครั้งของการเปรียบเทียบ ช่วงตัวเลือกถูกลดจาก $9$ ค่าเหลือเพียง $1$

ทำไม Binary search จึงเป็น $O(\log n)$

การเปรียบเทียบแต่ละครั้งจะตัดตัวเลือกที่เหลือออกไปประมาณครึ่งหนึ่ง หลังจากหนึ่งขั้นตอน จะเหลือประมาณ $n/2$ รายการ หลังจากสองขั้นตอน จะเหลือประมาณ $n/4$ รายการ หลังจาก $k$ ขั้นตอน ขนาดที่เหลือจะประมาณ

$$\frac{n}{2^k}$$

การค้นหาจะจบเมื่อปริมาณนี้มีค่าประมาณ $1$ ดังนั้นจำนวนขั้นตอนจึงเป็นไปตาม

$$2^k \approx n$$

เมื่อนำ $\log_2$ ทั้งสองข้าง จะได้ว่า

$$k \approx \log_2 n$$

นี่คือเหตุผลที่ Binary search ขยายขนาดได้ดี การค้นหาแบบเชิงเส้นอาจต้องตรวจมากถึง $n$ ครั้ง แต่ Binary search ต้องตรวจเพียงเท่าที่จำเป็นเพื่อหารช่วงให้เล็กลงครึ่งหนึ่งไปเรื่อย ๆ

ตัวอย่างโค้ด Binary search

นี่คือเวอร์ชันแบบวนซ้ำมาตรฐานใน Python: