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

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

Function interpolation_search ( A, n, x)

1 BEGIN
2 left := 1
3 right := n

/* ทำ�ซ้ำ�ตราบใดที่ ขอบทางซ้าย left น้อยกว่าหรือเท่ากับ ขอบทางขวา right */
4 WHILE (left <= right) DO
5 BEGIN
6 IF (A[left] = A[right]) THEN /* ค่าขอบซ้ายเท่ากับค่าขอบขวา */
7 IF A[left] = x) THEN /* และเท่ากับค่าที่สืบค้น */
8 RETURN left
9 ELSE

/* ไม่พบข้อมูล */
10 RETURN -1
11 adjust := (x - A[left]) / (A[right] - A[left])
12 IF (adjust < 0) OR (adjust > 1) THEN

/* ไม่พบข้อมูล */
13 RETURN -1

14 mid := round (left + adjust * (right – left))
15 IF (x < A[mid]) THEN /* ถ้าค่าที่สืบค้นน้อยกว่า */
16 right := mid – 1 /* ลดขอบขวาลง */
17 ELSE IF (x > A[mid]) THEN /* ถ้าค่าที่สืบค้นมากกว่า */
18 left := mid + 1 /* ขยับขอบซ้ายขึ้น */
19 ELSE /* พบข้อมูล */
20 RETURN mid
21 END

/* ไม่พบข้อมูล */
22 RETURN -1
23 END

การท�ำงาน
บรรทัดท่ี 2-3 ก�ำหนดค่าทางซ้าย (left) และขวา (right) เป็น 1 และ n ตามล�ำดับ
บรรทัดท่ี 4-21 ก�ำหนดการท�ำซ้�ำตราบใดที่ ขอบทางซ้าย left น้อยกว่าหรือเท่ากับ ขอบทางขวา right
บรรทัดที่ 6 ตรวจสอบว่าค่าทางซ้าย A[left] เท่ากับ ค่าทางขวา A[right] หรือไม่
บรรทัดที่ 7 ถ้าบรรทัดที่ 6 เป็นจริง และค่าทางซ้าย A[left] เท่ากับข้อมูลท่ีสืบค้น ให้ท�ำบรรทัดท่ี 8
บรรทัดที่ 8 ส่งค่ากลับเป็นต�ำแหน่งทางซ้าย