جستجوی فیبوناچی (Fibonacci Search) — به زبان ساده

آخرین به‌روزرسانی: ۱۱ خرداد ۱۳۹۸
زمان مطالعه: ۱۰ دقیقه
جستجوی فیبوناچی

در علوم کامپیوتر، «الگوریتم جستجو» (Search Algorithm)، الگوریتمی است که «مساله جستجو» (Search Problem) را حل می‌کند. در واقع، اطلاعات ذخیره شده درون ساختار داده، فضای جستجو یا دامنه مساله، با مقادیر گسسته یا پیوسته را بازیابی می‌کند. روش‌های جستجوی گوناگونی وجود دارند که از این جمله می‌توان به «جستجوی دودویی» (Binary Search)، «جستجوی درون‌یابی» (Interpolation Search)، «جستجوی پرشی» (Jump Search) و «جستجوی فیبوناچی» (Fibonacci Search) اشاره کرد. در این مطلب، الگوریتم جستجوی فیبوناچی مورد بررسی قرار گرفته و پیاده‌سازی آن با زبان‌های «سی» (C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

جستجوی فیبوناچی

یک آرایه مرتب شده []arr در اندازه n داده شده است و قرار است عنصر x در آن جستجو شود. «جستجوی فیبوناچی» (Fibonacci Search) اندیس x را در صورت وجود باز می‌گرداند و در صورتی که این عنصر در آرایه وجود نداشته باشد، اندیس ۱- را باز می‌گرداند. مثال زیر در این راستا قابل توجه است.

Input:  arr[] = {2, 3, 4, 10, 40}, x = 10
Output:  3
Element x is present at index 3.

Input:  arr[] = {2, 3, 4, 10, 40}, x = 11
Output:  -1
Element x is not present.

جستجوی فیبوناچی یک روش جستجوی «مبتنی بر مقایسه» (Comparison-Based) است که از اعداد فیبوناچی برای جستجوی یک عنصر در آرایه مرتب شده استفاده می‌کند.

شباهت‌های روش جستجوی فیبوناچی با جستجوی دودویی

  • برای آرایه‌های مرتب شده کار می‌کند.
  • یک الگوریتم «تقسیم و حل» (Divide and Conquer) است.
  • دارای پیچیدگی زمانی از مرتبه Log n است.

تفاوت‌ها با جستجوی دودویی

  • جستجوی فیبوناچی یک آرایه داده شده را به بخش‌های غیر هم‌اندازه تقسیم می‌کند.
  • جستجوی دودویی از عملگر تقسیم برای تقسیم بازه (Range) استفاده می‌کند. جستجوی فیبوناچی از / استفاده نمی‌کند، اما از عملگرهای + و – استفاده می‌کند. عملگرد تقسیم در برخی از «واحدهای پردازش مرکزی» (Central Processing Unit | CPU) دارای هزینه محاسباتی زیاد است.
  • جستجوی فیبوناچی عناصر نسبتا نزدیک‌تر را در گام‌های متوالی دنبال می‌کند. بنابراین، هنگامی که آرایه ورودی به اندازه‌ای بزرگ باشد که نتواند در کش CPU یا حتی در «رم» (RAM) برازش پیدا کند، جستجوی فیبوناچی مفید واقع می‌شود.

پیش‌زمینه

اعداد فیبوناچی به صورت بازگشتی F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1 تعریف می‌شوند. اولین اعداد فیبوناچی، 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 و 144 هستند و این دنباله به همین صورت ادامه دارد.

مشاهدات

مشاهده زیر برای محدود کردن بازه مورد استفاده قرار می‌گیرد و بنابراین، پیچیدگی زمانی از درجه ((O(log(n است.

F(n - 2) ≈ (1/3)*F(n) and 
F(n - 1) ≈ (2/3)*F(n

الگوریتم جستجوی فیبوناچی

فرض می‌شود عنصری که قرار است جستجو شود x است. ایده آن است که ابتدا کوچک‌ترین عدد فیبوناچی که بزرگ‌تر یا مساوی طول (اندازه) آرایه کنونی است یافته شود. عدد فیبوناچی یافت شده، در اینجا fib در نظر گرفته می‌شود. از (m-2)اُمین عدد فیبوناچی به عنوان اندیس استفاده می‌شود (اگر یک اندیس معتبر باشد). فرض می‌شود (m-2)‌اُمین عدد فیبوناچی i باشد، [arr[i با x مقایسه می‌شود، اگر مقدار آرایه در اندیس بیان شده با x برابر بود، i بازگردانده می‌شود؛ اگر x بزرگ‌تر بود، برای زیر آرایه بعد از i این مورد تکرار می‌شود و در غیر این صورت، (x کوچک‌تر بود) برای زیر آرایه پیش از i تکرار انجام می‌شود. در ادامه، الگوریتم کامل آورده شده است.

فرض می‌شود آرایه [arr[0..n-1، آرایه ورودی و عنصری که جستجو می‌شود x است.

  1. کوچک‌ترین عدد فیبوناچی بزرگ‌تر یا مساوی با n را پیدا کن. فرض می‌شود این عدد fibM [یعنی m‌اُمین عدد فیبوناچی] است. دو عدد فیبوناچی قبلی fibMm1 (یعنی (m-1)اُمین عدد فیبوناچی) و fibMm2 (یعنی (m-2)اُمین عدد فیبوناچی هستند).
  2. در حالی که آرایه دارای عناصری است که باید وارسی شوند:
    1. x را با آخرین عنصر از طیف پوشش داده شده با fibMm2 مقایسه کن.
    2. اگر x مطابق بود، اندیس را بازگردان.
    3. در غیر این صورت اگر x کمتر از عنصر است، سه متغیر فیبوناچی را دو تا فیبوناچی عقب ببر؛ این کار با هدف حذف تقریبا دو سوم باقیمانده از آرایه مورد استفاده قرار می‌گیرد.
    4. در غیر این صورت، x بزرگ‌تر از عنصر است؛ سه متغیر فیبوناچی را یک فیبوناچی عقب ببر، نقطه شروع را با مقدار اندیس بازنشانی کن. انجام این کارها موجب حذف یک سوم پیش روی باقیمانده از آرایه می‌شود.
  3.  از آنجا که ممکن است تنها یک عنصر برای مقایسه باقی مانده باشد، بررسی کن که fibMm1 برابر با ۱ است یا خیر. اگر پاسخ بلی بود، x را با عنصر باقیمانده مقایسه کن و در صورت مطابقت داشتن، اندیس را باز گردان.

پیاده‌سازی جستجوی فیبوناچی در C

// C program for Fibonacci Search 
#include <stdio.h> 
  
// Utility function to find minimum of two elements 
int min(int x, int y) { return (x<=y)? x : y; } 
  
/* Returns index of x if present,  else returns -1 */
int fibMonaccianSearch(int arr[], int x, int n) 
{ 
    /* Initialize fibonacci numbers */
    int fibMMm2 = 0;   // (m-2)'th Fibonacci No. 
    int fibMMm1 = 1;   // (m-1)'th Fibonacci No. 
    int fibM = fibMMm2 + fibMMm1;  // m'th Fibonacci 
  
    /* fibM is going to store the smallest Fibonacci 
       Number greater than or equal to n */
    while (fibM < n) 
    { 
        fibMMm2 = fibMMm1; 
        fibMMm1 = fibM; 
        fibM  = fibMMm2 + fibMMm1; 
    } 
  
    // Marks the eliminated range from front 
    int offset = -1; 
  
    /* while there are elements to be inspected. Note that 
       we compare arr[fibMm2] with x. When fibM becomes 1, 
       fibMm2 becomes 0 */
    while (fibM > 1) 
    { 
        // Check if fibMm2 is a valid location 
        int i = min(offset+fibMMm2, n-1); 
  
        /* If x is greater than the value at index fibMm2, 
           cut the subarray array from offset to i */
        if (arr[i] < x) 
        { 
            fibM  = fibMMm1; 
            fibMMm1 = fibMMm2; 
            fibMMm2 = fibM - fibMMm1; 
            offset = i; 
        } 
  
        /* If x is greater than the value at index fibMm2, 
           cut the subarray after i+1  */
        else if (arr[i] > x) 
        { 
            fibM  = fibMMm2; 
            fibMMm1 = fibMMm1 - fibMMm2; 
            fibMMm2 = fibM - fibMMm1; 
        } 
  
        /* element found. return index */
        else return i; 
    } 
  
    /* comparing the last element with x */
    if(fibMMm1 && arr[offset+1]==x)return offset+1; 
  
    /*element not found. return -1 */
    return -1; 
} 
  
/* driver function */
int main(void) 
{ 
    int arr[] = {10, 22, 35, 40, 45, 50, 80, 82, 
                 85, 90, 100}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int x = 85; 
    printf("Found at index: %d", 
            fibMonaccianSearch(arr, x, n)); 
    return 0; 
}

پیاده‌سازی جستجوی فیبوناچی در جاوا

// Java program for Fibonacci Search 
import java.util.*; 
  
class Fibonacci 
{    
    // Utility function to find minimum  
    // of two elements 
    public static int min(int x, int y)  
    { return (x <= y)? x : y; } 
  
    /* Returns index of x if present, else returns -1 */
    public static int fibMonaccianSearch(int arr[],  
                                         int x, int n) 
    { 
        /* Initialize fibonacci numbers */
        int fibMMm2 = 0; // (m-2)'th Fibonacci No. 
        int fibMMm1 = 1; // (m-1)'th Fibonacci No. 
        int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci 
  
        /* fibM is going to store the smallest  
        Fibonacci Number greater than or equal to n */
        while (fibM < n) 
        { 
            fibMMm2 = fibMMm1; 
            fibMMm1 = fibM; 
            fibM = fibMMm2 + fibMMm1; 
        } 
  
        // Marks the eliminated range from front 
        int offset = -1; 
  
        /* while there are elements to be inspected.  
        Note that we compare arr[fibMm2] with x.  
        When fibM becomes 1, fibMm2 becomes 0 */
        while (fibM > 1) 
        { 
            // Check if fibMm2 is a valid location 
            int i = min(offset+fibMMm2, n-1); 
  
            /* If x is greater than the value at  
            index fibMm2, cut the subarray array  
            from offset to i */
            if (arr[i] < x) 
            { 
                fibM = fibMMm1; 
                fibMMm1 = fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
                offset = i; 
            } 
  
            /* If x is greater than the value at index  
            fibMm2, cut the subarray after i+1 */
            else if (arr[i] > x) 
            { 
                fibM = fibMMm2; 
                fibMMm1 = fibMMm1 - fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
            } 
  
            /* element found. return index */
            else return i; 
        } 
  
        /* comparing the last element with x */
        if(fibMMm1 == 1 && arr[offset+1] == x) 
            return offset+1; 
  
        /*element not found. return -1 */
        return -1; 
    } 
      
    // driver code 
    public static void main(String[] args) 
    { 
        int arr[] = {10, 22, 35, 40, 45, 50,  
                     80, 82, 85, 90, 100}; 
        int n = 11; 
        int x = 85; 
        System.out.print ("Found at index: "+ 
                   fibMonaccianSearch(arr, x, n)); 
    } 
} 
  
// This code is contributed by rishabh_jain

پیاده‌سازی جستجوی فیبوناچی در پایتون ۳

# Python3 program for Fibonacci search. 
from bisect import bisect_left 
  
# Returns index of x if present,  else  
# returns -1  
def fibMonaccianSearch(arr, x, n): 
      
    # Initialize fibonacci numbers  
    fibMMm2 = 0 # (m-2)'th Fibonacci No. 
    fibMMm1 = 1 # (m-1)'th Fibonacci No. 
    fibM = fibMMm2 + fibMMm1 # m'th Fibonacci 
  
    # fibM is going to store the smallest  
    # Fibonacci Number greater than or equal to n  
    while (fibM < n): 
        fibMMm2 = fibMMm1 
        fibMMm1 = fibM 
        fibM = fibMMm2 + fibMMm1 
  
    # Marks the eliminated range from front 
    offset = -1; 
  
    # while there are elements to be inspected. 
    # Note that we compare arr[fibMm2] with x. 
    # When fibM becomes 1, fibMm2 becomes 0  
    while (fibM > 1): 
          
        # Check if fibMm2 is a valid location 
        i = min(offset+fibMMm2, n-1) 
  
        # If x is greater than the value at  
        # index fibMm2, cut the subarray array  
        # from offset to i  
        if (arr[i] < x): 
            fibM = fibMMm1 
            fibMMm1 = fibMMm2 
            fibMMm2 = fibM - fibMMm1 
            offset = i 
  
        # If x is greater than the value at  
        # index fibMm2, cut the subarray  
        # after i+1 
        elif (arr[i] > x): 
            fibM = fibMMm2 
            fibMMm1 = fibMMm1 - fibMMm2 
            fibMMm2 = fibM - fibMMm1 
  
        # element found. return index  
        else : 
            return i 
  
    # comparing the last element with x */ 
    if(fibMMm1 and arr[offset+1] == x): 
        return offset+1; 
  
    # element not found. return -1  
    return -1
  
# Driver Code 
arr = [10, 22, 35, 40, 45, 50, 
       80, 82, 85, 90, 100] 
n = len(arr) 
x = 85
print("Found at index:", 
      fibMonaccianSearch(arr, x, n)) 
  
# This code is contributed by rishabh_jain

پیاده‌سازی جستجوی فیبوناچی در #C

// C# program for Fibonacci Search 
using System; 
  
class GFG { 
      
    // Utility function to find minimum  
    // of two elements 
    public static int min(int x, int y)  
    { 
        return (x <= y)? x : y;  
    } 
  
    /* Returns index of x if present, else returns -1 */
    public static int fibMonaccianSearch(int []arr,  
                                        int x, int n) 
    { 
        /* Initialize fibonacci numbers */
        int fibMMm2 = 0; // (m-2)'th Fibonacci No. 
        int fibMMm1 = 1; // (m-1)'th Fibonacci No. 
        int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci 
  
        /* fibM is going to store the smallest  
        Fibonacci Number greater than or equal to n */
        while (fibM < n) 
        { 
            fibMMm2 = fibMMm1; 
            fibMMm1 = fibM; 
            fibM = fibMMm2 + fibMMm1; 
        } 
  
        // Marks the eliminated range from front 
        int offset = -1; 
  
        /* while there are elements to be inspected.  
        Note that we compare arr[fibMm2] with x.  
        When fibM becomes 1, fibMm2 becomes 0 */
        while (fibM > 1) 
        { 
            // Check if fibMm2 is a valid location 
            int i = min(offset+fibMMm2, n-1); 
  
            /* If x is greater than the value at  
            index fibMm2, cut the subarray array  
            from offset to i */
            if (arr[i] < x) 
            { 
                fibM = fibMMm1; 
                fibMMm1 = fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
                offset = i; 
            } 
  
            /* If x is greater than the value at index  
            fibMm2, cut the subarray after i+1 */
            else if (arr[i] > x) 
            { 
                fibM = fibMMm2; 
                fibMMm1 = fibMMm1 - fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
            } 
  
            /* element found. return index */
            else return i; 
        } 
  
        /* comparing the last element with x */
        if(fibMMm1 == 1 && arr[offset+1] == x) 
            return offset + 1; 
  
        /*element not found. return -1 */
        return -1; 
    } 
      
    // driver code 
    public static void Main() 
    { 
        int []arr = {10, 22, 35, 40, 45, 50,  
                    80, 82, 85, 90, 100}; 
        int n = 11; 
        int x = 85; 
        Console.Write ("Found at index: " + 
                fibMonaccianSearch(arr, x, n)); 
    } 
} 
  
// This code is contributed by nitin mittal.

پیاده‌سازی جستجوی فیبوناچی در PHP

<?php 
// PHP program for Fibonacci Search 
  
/* Returns index of x if present, else returns -1 */
function fibMonaccianSearch($arr, $x, $n) 
{ 
    /* Initialize fibonacci numbers */
    $fibMMm2 = 0; // (m-2)'th Fibonacci No. 
    $fibMMm1 = 1; // (m-1)'th Fibonacci No. 
    $fibM = $fibMMm2 + $fibMMm1; // m'th Fibonacci 
  
    /* fibM is going to store the smallest Fibonacci 
    Number greater than or equal to n */
    while ($fibM < $n) 
    { 
        $fibMMm2 = $fibMMm1; 
        $fibMMm1 = $fibM; 
        $fibM = $fibMMm2 + $fibMMm1; 
    } 
  
    // Marks the eliminated range from front 
    $offset = -1; 
  
    /* while there are elements to be inspected. Note that 
    we compare arr[fibMm2] with x. When fibM becomes 1, 
    fibMm2 becomes 0 */
    while ($fibM > 1) 
    { 
        // Check if fibMm2 is a valid location 
        $i = min($offset+$fibMMm2, $n-1); 
  
        /* If x is greater than the value at index fibMm2, 
        cut the subarray array from offset to i */
        if ($arr[$i] < $x) 
        { 
            $fibM = $fibMMm1; 
            $fibMMm1 = $fibMMm2; 
            $fibMMm2 = $fibM - $fibMMm1; 
            $offset = $i; 
        } 
  
        /* If x is greater than the value at index fibMm2, 
        cut the subarray after i+1 */
        else if ($arr[$i] > $x) 
        { 
            $fibM = $fibMMm2; 
            $fibMMm1 = $fibMMm1 - $fibMMm2; 
            $fibMMm2 = $fibM - $fibMMm1; 
        } 
  
        /* element found. return index */
        else return $i; 
    } 
  
    /* comparing the last element with x */
    if($fibMMm1 && $arr[$offset + 1] == $x)return $offset+1; 
  
    /*element not found. return -1 */
    return -1; 
} 
  
/* driver code */
    $arr = array(10, 22, 35, 40, 45, 50, 80, 82,85, 90, 100); 
    $n = count($arr); 
    $x = 85; 
    printf("Found at index: ".fibMonaccianSearch($arr, $x, $n)); 
  
// This code is contributed by mits 
?>

خروجی:

Found at index: 8

مثال از الگوریتم جستجوی فیبوناچی

برای درک بهتر الگوریتم، مثال زیر قابل توجه است.

جستجوی فیبوناچی

فرضیه: اندیس‌گذاری از ۱ شروع می‌شود. عنصر هدف ۸۵ و طول آرایه n=11 است.

  • کوچک‌ترین عدد فیبوناچی بزرگ‌تر یا مساوی ۱۱، برابر با ۱۳ است. همانطور که در تصویر مشهود است، fibMm1 = 8 ،fibMm2 = 5 و fibM = 13 است.
  • دیگر جزئیات پیاده‌سازی متغیر اُفسِت (مقداردهی اولیه آن با صفر انجام شده) عبارتند از اینکه، این متغیر طیفی که حذف شده را مشخص می‌کند که از جلو آغاز می‌شود و همچنین، متغیر لحظه به لحظه به روز رسانی می‌شود.

اکنون با توجه به اینکه مقدار افست برابر با اندیس است و همه اندیس‌های شامل آن و مقادیر زیر آن حذف شده‌اند، تنها کاری که می‌تواند معنادار باشد افزودن چیزی به آن است. از آنجا که fibMm2 تقریبا یک سوم از آرایه را نشانه‌گذاری می‌کند و در عین حال اندیس‌هایی که علامت‌گذاری می‌کند اندیس‌های معتبری هستند، می‌توان fibMm2 را به offset افزود و عنصر در اندیس  (i = min(offset + fibMm2, n را بررسی کرد.

جستجوی فیبوناچی

بصری‌سازی:

جستجوی فیبوناچی

تحلیل پیچیدگی

بدترین حالت هنگامی است که هدف در ۲/۳ بزرگ‌تر آرایه باشد و فرایند جستجو تا پیدا کردن آن ادامه پیدا کند. به بیان دیگر، هر بار ۱/۳ کوچک‌تر آرایه حذف می‌شود. فراخوانی یک بار برای n، بار دیگر برای $$ (2/3) n$$، سپس برای $$ (4/9) n $$ و به همین صورت انجام می‌شود. این مورد را می‌توان به صورت زیر در نظر گرفت.

جستجوی فیبوناچی

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۴ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
geeksforgeeks
One thought on “جستجوی فیبوناچی (Fibonacci Search) — به زبان ساده

سلام if($fibMMm1 && $arr[$offset + 1] == $x)return $offset+1;
مثال مورد استفاده بودن این خط را میشه بفرمایید

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *