Page 34 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 34
15-24 โครงสร้างข้อมูลและขั้นต อนว ิธี
ข้อมูลท ่ีส ่งกลับ
ถ้าพบข้อมูลที่ส ืบค้น ค่าที่ส่งก ลับจ ะเป็นต�ำแหน่งข องข้อมูลในอ าร์เรย์
ถ้าไม่พ บข ้อมูลท ี่สืบค้น ค่าที่ส ่งกลับจะเป็นต�ำแหน่งท ่ีไม่มีจริงในอ าร์เรย์น่ันคือ -1
Function BinarySearch (A, n, x)
1 BEGIN
2 left := 1
3 right := n
4 WHILE (left <= right ) DO
5 BEGIN
6 pos := (left + right)/2
7 IF ( x = A[pos] ) THEN
8 RETURN pos
9 ELSE IF (x < A[pos]) THEN
10 right := pos – 1
11 ELSE
12 left := pos + 1
13 END
14 RETURN -1
15 END
การท �ำงาน
บรรทัดที่ 2 เป็นการก�ำหนดค ่าข อบซ ้ายสุดให้เป็น 1
บรรทัดท ี่ 3 เป็นการก�ำหนดค ่าข อบข วาสุดให้เป็น n
ซ่ึงท ั้งส องบรรทัดน ี้เป็นการก �ำหนดช ่วงการพ ิจารณาค รั้งแรกให้เป็นจ�ำนวนข ้อมูลท ั้งหมด
บรรทัดที่ 4-13 ก�ำหนดให้ท�ำซ้ําตราบใดท่ีค ่าขอบซ้ายน้อยกว่าหรือเท่ากับข อบขวา
บรรทัดท ี่ 6 ก�ำหนดให้ต�ำแหน่งที่ตรวจส อบข ้อมูลเป็นต �ำแหน่งตรงกลางร ะหว่างขอบซ ้ายและข วา
บรรทัดที่ 7 เปรียบเทียบข ้อมูลที่สืบค้นว ่าเท่ากับค ่าป ัจจุบันของอาร์เรย์หรือไม่
บรรทัดท ี่ 8 ถ้าเท่ากัน ให้ส ่งค ่ากลับเป็นต �ำแหน่งท ่ีพ บคือ pos
บรรทัดท ี่ 9 เปรียบเทียบข้อมูลที่สืบค้นว่าน้อยกว่าค่าป ัจจุบันของอ าร์เรย์ห รือไม่
บรรทัดท ี่ 10 ถ้าน้อยกว่า ให้ปรับขอบขวาลงมาเป็น pos-1 นั่นคือลดขนาดข้อมูลที่ตรวจสอบมาเหลือแค่
ครึ่งซ้าย
บรรทัดท่ี 12 ถ้าบรรทัดที่ 7 และ บรรทัดท่ี 9 ไม่เป็นจ ริง บรรทัดท ี่ 12 ปรับข อบซ ้ายข ึ้นไปเป็น pos+1 น่ัน
คือล ดข นาดข ้อมูลที่ตรวจสอบมาเหลือแค่ครึ่งขวา
บรรทัดที่ 14 ถ้าท�ำซ้ําตั้งแต่บรรทัดท่ี 4 จนถึง 13 จนขอบซ้ายมากกว่าขอบขวาแล้วไม่พบค่าท่ีสืบค้น
ให้ส ่งค่าก ลับเป็นต �ำแหน่ง -1
