Page 37 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 37
ขั้นต อนว ิธีการค ้นหาข ้อมูล 15-27
รอบท ี่ 4
5 24 33 43 68 73 90 91
left = 3 right = 3
pos = (3 + 3)/2 = 3
A[pos] = 33
X = 34
- จากค่าข อบซ้ายแ ละขวา left = 3 และ right = 3 หาต�ำแหน่งก ่ึงกลางระหว่างซ ้ายแ ละขวา
pos = (left + right) / 2
= (3 + 3) /2
= 3
- เปรียบเทียบค่า x = 34 กับค ่า A[3] = 33 ซึ่งค่า x มากกว่า
- ให้สืบค้นจากส ่วนท างข วา โดยป รับข อบซ้าย
left = pos + 1
= 3 + 1
= 4
รอบท ี่ 5
- เน่ืองจากขอบซ้าย 4 มากกว่าข อบขวา 3 ดังน ้ัน โปรแกรมออกจ ากการวนรอบ
- ส่งค ่าก ลับเป็นต �ำแหน่งท ่ีไม่พ บค ือ -1
4. วเิ คราะห์ประสิทธิภาพของขั้นตอนวธิ ีการคน้ หาข้อมูลแบบทวิภาค
การว ิเคราะห์ประสิทธิภาพน้ันจะพิจารณาจากลักษณะก ารค้นหาข ้อมูลท ่ีได้ 3 แบบ ดังนี้
4.1 กรณดี ีท่ีสุด
กรณีน ี้ข ้อมูลท ี่ต ้องการค้นหาอ ยู่เป็นสมาชิกต รงกึ่งกลางข องอาร์เรย์เช่น
ข้อมูลท ่ีต้องการค้นหา คือ 16
ข้อมูล 1 7 15 16 23 32 34
การค้นหาลักษณะนี้จะใช้การเปรียบเทียบแค่ค รั้งเดียวเสมอดังน้ันประสิทธิภาพเชิงเวลาเท่ากับ O(1)
4.2 กรณีแยท่ ี่สุด
กรณีน ้ีข ้อมูลท ี่ต้องการค้นหาไม่อยู่ในอาร์เรย์เช่น
ข้อมูลท ี่ต ้องการค ้นหา คือ 33
ข้อมูล 1 7 15 16 23 32 34
การค้นหาลักษณะนี้จะใช้การเปรียบเทียบวนซ้ําจนกว่าขอบซ้ายมีค่ามากกว่าขอบขวา โดยการวนซ้ํา
N
แต่ละค ร้ังจ ะล ดจ�ำนวนข ้อมูลลงเหลือ N/2 ซึ่งก ารว นซ้ําครั้งส ุดท้ายเกิดข้ึนเม่ือ 2k ≥ 1 ดังน ้ัน
