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