Page 41 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 41
ขั้นต อนวิธีก ารค้นหาข ้อมูล 15-31
- จากค่าข อบซ้ายและขวา left = 5 และ right = 8 หาต �ำแหน่งก ่ึงกลางระหว่างซ ้ายและขวา
pos = (left + right)/2
= (5 + 8)/2
≅ 6
- เปรียบเทียบค ่า x = 69 กับค่า A[6] = 73 ซ่ึงค ่า x น้อยก ว่า
- ปรับขอบข วาลงมา
right = pos
= 6
รอบท ่ี 3
5 24 33 43 68 73 90 91
left = 5 right = 6
pos = (5 + 6)/2 = 5
A[pos] = 68
X = 69
- จากค่าข อบซ้ายและข วา left = 5 และ right = 6 หาต�ำแหน่งก่ึงกลางระห ว่างซ้ายแ ละข วา
pos = (left + right)/2
= (5 + 6)/2
≅ 5
- เปรียบเทียบค ่า x = 69 กับค ่า A[5] = 68 ซึ่งค่า x มากกว่า
- ให้ปรับข อบซ ้ายขึ้นม า
left = pos + 1
= 5 + 1
= 6
รอบท่ี 4
- เนื่องจากขอบซ้าย 6 เท่ากว่าขอบข วา 6 ดังนั้นโปรแกรมออกจ ากก ารวนร อบ
- เปรียบเทียบค่า x = 69 กับค่า A[left] = A[6] =73 ซึ่งค่า x น้อยกว่า ส่งค่ากลับเป็นต�ำแหน่งขอบซ้าย
นั่นคือ 6
5 24 33 43 68 73 90 91
left = 6
