กลวิธีการค้นหาแบบฟีโบนัชชี

ในวิทยาการคอมพิวเตอร์ กลวิธีการค้นแบบฟีโบนัชชี  เป็นกลวิธีการค้นโดยนำเอาจำนวนฟีโบนัชชีมาสร้างเป็นกลวิธีค้นตำแหน่งของข้อมูลในแถวลำดับ ที่ได้รับการเรียงลำดับแล้วโดยใช้หลักการของขั้นตอนวิธีการแบ่งแยกและเอาชนะ ซึ่งเป็นหลักการเดียวกับที่ใช้ในกลวิธีการค้นหาแบบทวิภาค
แต่เมื่อเปรียบเทียบกับกลวิธีการค้นแบบเลขคู่แล้วกลวิธีการค้นแบบฟีโบนัชชีจะมีการตรวจสอบตำแหน่งของข้อมูลโดยใช้การกระจายตัวที่น้อยกว่า ทำให้เกิดข้อได้เปรียบเมื่อใช้กลวิธีการค้นแบบฟีโบนัชชีกับข้อมูลที่ถูกเก็บอยู่ในแหล่งเก็บข้อมูลไม่มีรูปแบบ ซึ่งเวลาในการใช้ค้นตำแหน่งของข้อมูลที่ต้องการในแหล่งข้อมูลดังกล่าวจะขึ้นอยู่กับตำแหน่งของข้อมูลที่ได้มีการเข้าถึงครั้งล่าสุด ยกตัวอย่างแหล่งข้อมูลแบบไม่มีรูปแบบอาธิเช่น แถบบันทึก ที่ซึ่งเวลาในการเข้าถึงข้อมูลใดๆในแถบแม่เหล็กจะขึ้นอยู่กับระยะทางระหว่างข้อมูลนั้นกับข้อมูลที่หัวของแถบแม่เหล็กกำลังอ่านอยู่ ทั้งนี้กลวิธีการค้นแบบฟีโบนัชชียังมีข้อได้เปรียบในการค้นข้อมูลในแคช (Cache) หรือแรม (Ram) ซึ่งเป็นแหล่งข้อมูลแบบไม่มีรูปแบบอีกด้วยเช่นกัน
ลักษณะทั่วไป.
กลวิธีการค้นแบบฟีโบนัชชีใช้หลักการของขั้นตอนวิธีโดยการแบ่งแยกและเอาชนะโดยการตัดถอนข้อมูลในส่วนที่ไม่สนใจออกจนได้ตำแหน่งของข้อมูลที่ต้องการ การตัดถอนครั้งหนึ่งจะตัดถอนเป็นจำนวนในลำดับของจำนวนฟีโบนัชชี และจะลดค่าของลำดับลงเรื่อยๆทุกครั้งที่พิจารณาเสร็จ กลวิธีการค้นแบบฟีโบนัชชีจะสิ้นสุดลงก็ต่อเมื่อเจอตำแหน่งของข้อมูลที่สนใจหรือค้นแล้วไม่พบว่ามีข้อมูลที่สนใจปรากฏอยู่ในแหล่งข้อมูลเลย
ขั้นตอนวิธี.
ให้ F คือแถวลำดับของจำนวนฟีโบนัชชี ให้ "k" คือค่าของข้อมูลใดๆใน"F" "n"คือขนาดของแถวลำดับของข้อมูล ถ้า "n" เป็นเลขฟีโบนนัชชีให้ "Fm=n" แต่ถ้า "n" ไม่ใช่จำนวนฟีโบนัชชีให้ "Fm" เป็นจำนวนฟีโบนัชชีที่มากกว่า "n" แต่ใกล้เคียงที่สุด นิยามให้ค่าใน "F" เหมือนกับลำดับฟีโบนนัชชีโดยให้ "Fk+2=Fk+1+Fk" โดยที่ "k≥0 ,F1=1" และ "F0=0"
 การหาตำแหน่งของข้อมูลที่สนใจสามารถหาตำแหน่งได้โดยทำตามขั้นตอนต่อไปนี้
 นอกจากนี้ยังมีขั้นตอนวิธีอื่นๆอีกดังต่อไปนี้
ให้ "R" เป็นตารางที่เก็บสถิติขนาด "n" ช่อง ให้ ที่มีการเพิ่มขึ้นของลำดับ "K" โดยที่ "K1 < K2 < ... < Kn" ขั้นตอนวิธีนี้จะหาข้อมูลที่ต้องการตามค่าของ "K" โดยจะสมมติว่า "N+1 = Fk+1"ซึ่งหาก "N+1"ไม่ใช่จำนวนฟีโบนัชชีก็ให้ใช้หลักเกณฑ์การเปลี่ยนเป็นจำนวนฟีโบนัชชีเช่นเดียวกับขั้นตอนวิธีแรก โดยให้ "X" เป็นข้อมูลที่ต้องการจะหา
 ขั้นที่หนึ่ง ให้ "i ← Fk,p ← Fk-1,q ← Fk-2" โดยจากขั้นตอนวิธีจะได้ว่า "p" และ "q" เป็นลำดับจำนวนฟีโบนัชชีที่ต่อเนื่องกัน
 ขั้นที่สอง ถ้า "X < i" ให้ไปทำขั้นที่สาม ถ้า "X > i" ให้ไปทำขั้นตอนที่สี่ แต่ถ้า "X = i" จะหมายถึงว่าค้นเจอตำแหน่งของข้อมูลแล้ว คำตอบคือที่ตำแหน่ง"k" ให้จบการทำงาน
 ขั้นที่สาม ถ้า "q = 0" จะหมายถึงว่าค้นไม่เจอข้อมูลที่ต้องการและให้จบการทำงาน ถ้าไม่เช่นนั้นให้ "i ← i - q" ให้ "p ← q แล้วจึงให้ q ← q - p" จากนั้นกลับไปทำขั้นตอนที่สอง
 ขั้นที่สี่ ถ้า "p = 1" จะหมายถึงว่าค้นไม่เจอข้อมูลที่ต้องการและให้จบการทำงาน ถ้าไม่เช่นนั้นให้ "i ← i + q" ให้ "p ← p - q" แล้วจึงให้ "q ← q - p" จากนั้นกลับไปทำขั้นตอนที่สอง
ตัวอย่างการใช้ขั้นตอนวิธี.
ให้ "R" เป็นแถวลำดับขนาด "13" ช่องมีข้อมูลคือ {1, 4, 5, 7, 9, 11, 13, 16, 18, 20, 25, 27, 30} ต้องการหาว่า "9" อยู่ในตำแหน่งที่เท่าไหร่ในแถวลำดับ
 เนื่องจาก "13"เป็นจำนวนฟีโบนัชชีจึงให้ "F" เป็นแถวลำดับขนาดเท่ากันและให้ x = 9
1. กำหนดให้ "i = F13, p = F8, q = F5" (ขั้นตอนที่หนึ่ง)
2. เนื่องจาก "x < i" (ขั้นตอนที่สอง) จึงกำหนดค่าใหม่ให้ "i = F8, p = F5 , q = F3 " (ขั้นตอนที่สาม)
3. เนื่องจาก "x < i" (ขั้นตอนที่สอง) จึงกำหนดค่าใหม่ให้ "i = F5, p = F3 , q = F2 " (ขั้นตอนที่สาม)
4. เนื่องจาก x = i จึงได้ว่าค้นเจอค่า "9" ในแถวลำดับที่ช่อง "K = 5" (ขั้นตอนที่สอง)
 จากทฤษฎีสำคัญ  จะได้ว่าประสิทธิภาพเชิงเวลาคือ
 <math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n) \;\;\;\; \mbox{where} \;\; a \geq 1 \mbox{, } b > 1</math>
 กลวิธีการค้นแบบฟีโบนัชชีแบ่งการเรียกซ้ำออกเป็นสองส่วนจึงได้ว่าส่วนการเรียกซ้ำคือ <math>T(n/2)</math> และส่วนภาระจริงนั้นมีการทำงานเป็น <math>\Theta\left(1 \right)</math> เมื่อรวมกันแล้วประสิทธิภาพเชิงเวลาของกลวิธีการค้นแบบฟีโบนัชชีมีค่าเป็น
 <math>T(n) = T(n/2) + \Theta\left(1 \right)</math> หรือคิดเป็น O(log(n))
หัวข้ออื่นๆที่เกี่ยวข้อง.
Golden section search
Binary search algorithm