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

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

Function fibonacci_search (A, n, x)

1 BEGIN
2 f1 := 1 /* กำ�หนดค่าเริ่มต้นเลข Finonacci f1 และ f2 */
3 f2 := 0
4 mid := 2
5 WHILE ( f1 < n ) DO /* ทำ�ซ้ำ�ถ้าขอบบน f1 น้อย กว่า n */
6 BEGIN
7 f1 := f1 + f2
8 f2 := f1 - f2
9 mid := mid + 1
10 END
11 f2 := f1 - f2 /* ปรับขนาด f2 และ f1 โดยถอยลงมา 1 ค่า */
12 f1 := f1 - f2
13 mid := mid - 1
14 first := 0
15 WHILE ( mid > 0 ) DO /* สืบค้นค่าที่ต้องการพร้อมปรับช่วงการค้นหา */
16 BEGIN
17 index := first + f1

/* ตรวจสอบค่าที่ค้นหาถ้าน้อยกว่า ปรับขอบล่างแล้วปรับขอบบน */
18 IF (index >= n) OR (x < A[index]) THEN
19 BEGIN
20 mid := mid -1
21 f2 := f1 - f2
22 f1 := f1 - f2
23 END
24 ELSE IF (x = A[index]) THEN /* ตรวจสอบค่าที่ค้นหา ถ้าเจอให้ส่งค่ากลับ */
25 RETURN index
26 ELSE /* ถ้าไม่ใช่กรณีข้างต้น ปรับขอบบนแล้วปรับขอบล่าง */
27 BEGIN
28 first := index
29 mid := mid - 2
30 f1 := f1 - f2
31 f2 := f2 - f1
32 END
33 END
34 RETURN -1
35 END