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