Page 39 - โครงสร้างข้อมูลและขั้นตอนวิธี

P. 39

ขั้นต อนว ิธีการค้นหาข ้อมูล 15-29

ข้อมูลท ี่ส่งกลับ
ถ้าห าค ่าข อบล ่างได้ ค่าท่ีส่งก ลับจ ะเป็นต �ำแหน่งข องข้อมูลในอาร์เรย์
ถ้าไม่สามารถหาข อบล ่างได้ ค่าที่ส ่งกลับจ ะเป็นต�ำแหน่งที่ไม่มีจริงในอาร์เรย์น่ันคือ -1

Function LowerBoundSearch (A, n, x)

1 BEGIN
2 left := 1
3 right := n
4 WHILE left < right DO
5 pos := (left+right)/2
6 IF x <= A[pos] THEN
7 right := pos
8 ELSE
9 left := pos+1
10 END
11 IF x <= A[left] THEN
12 RETURN left
13 ELSE
14 RETURN -1
15 END

การท �ำงาน
บรรทัดที่ 2 เป็นการก �ำหนดค่าข อบซ ้ายส ุดให้เป็น 1
บรรทัดท ี่ 3 เป็นการก �ำหนดค ่าข อบขวาส ุดให้เป็น n
ซ่ึงทั้งส องบ รรทัดนี้เป็นการก�ำหนดช่วงการพิจารณาครั้งแรกให้เป็นจ�ำนวนข ้อมูลท ั้งหมด
บรรทัดท ี่ 4-10 วนซ้ําตราบใดที่ข อบซ ้ายน้อยก ว่าข อบขวา
บรรทัดที่ 5 ก�ำหนดให้ต�ำแหน่งท่ีต รวจส อบข้อมูลเป็นต�ำแหน่งต รงกลางร ะหว่างขอบซ ้ายและข วา
บรรทัดที่ 6 เปรียบเทียบข้อมูลที่ส ืบค้นว่าน ้อยก ว่าหรือเท่ากับค่าป ัจจุบันของอ าร์เรย์หรือไม่
บรรทัดท ี่ 7 ถ้าน้อยก ว่า ให้ปรับขอบข วาล งมาเป็น pos
บรรทัดที่ 8 ถ้าไม่น ้อยกว่า บรรทัดท่ี 9 ปรับข อบซ้ายข้ึนไปเป็น pos+1
บรรทัดที่ 11 เปรียบเทียบค่า x ว่าน้อยกว่าห รือเท่ากับค ่าท่ีขอบซ ้าย หรือไม่
บรรทัดท ี่ 12 ถ้าน ้อยกว่าหรือเท่ากับ ให้ส ่งค่ากลับเป็นต �ำแหน่งของข อบซ้าย
บรรทัดท ี่ 14 ถ้าค ่า x มากกว่าค่าที่ขอบซ้าย ให้ส่งค ่าก ลับเป็นต�ำแหน่ง -1

34 35 36 37 38 39 40 41 42 43 44