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

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

2. ขั้น​ตอนว​ ธิ กี ารค้นหาขอ้ มลู แบบกระโดด
ข้ันต​ อน​วิธี JumpSearch มี​ราย​ละเอียด​ดังน้ี

ข้อมูลเ​ข้าป​ ระกอบ​ด้วย

อาร์เรย์​ข้อมูล​ที่เ​รียงล​ �ำดับไ​ว้​แล้ว A

จ�ำนวนข​ ้อมูล​ทั้งหมด n

ค่าท่ี​ต้องการ​ค้นหา x

ข้อมูล​ที่ส​ ่งก​ ลับ

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

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

Function JumpSearch (A, n, x)

1 BEGIN
/* กำ�หนดค่าที่จะกระโดด */

2 k := square_root(n)
3 step := k
4 prev := 1

/* หาช่วงที่น่าจะมีข้อมูล */
5 WHILE (step < n) AND (A[step] < x) DO
6 BEGIN
7 prev := step
8 step := step + k
9 END
10 IF ( step > n) THEN
11 step := n
12
13 IF ( A[step] = x ) THEN
14 RETURN step
15 /* สืบค้นข้อมูลภายในช่วงที่กำ�หนด */
16 WHILE (A[prev] < x) DO
17 prev := prev + 1
18 IF (prev = step) THEN
19 RETURN -1
20 END
21 /* ตรวจสอบว่าพบข้อมูลหรือไม่ */
22 IF (A[prev] = x) THEN
23 RETURN prev
24 ELSE
25 RETURN -1
26 END