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

۴۲۸ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۱۰ دقیقه
جستجوی فیبوناچی (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 است.

1F(n - 2)(1/3)*F(n) and 
2F(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

1// C program for Fibonacci Search 
2#include <stdio.h> 
3  
4// Utility function to find minimum of two elements 
5int min(int x, int y) { return (x<=y)? x : y; } 
6  
7/* Returns index of x if present,  else returns -1 */
8int fibMonaccianSearch(int arr[], int x, int n) 
9{ 
10    /* Initialize fibonacci numbers */
11    int fibMMm2 = 0;   // (m-2)'th Fibonacci No. 
12    int fibMMm1 = 1;   // (m-1)'th Fibonacci No. 
13    int fibM = fibMMm2 + fibMMm1;  // m'th Fibonacci 
14  
15    /* fibM is going to store the smallest Fibonacci 
16       Number greater than or equal to n */
17    while (fibM < n) 
18    { 
19        fibMMm2 = fibMMm1; 
20        fibMMm1 = fibM; 
21        fibM  = fibMMm2 + fibMMm1; 
22    } 
23  
24    // Marks the eliminated range from front 
25    int offset = -1; 
26  
27    /* while there are elements to be inspected. Note that 
28       we compare arr[fibMm2] with x. When fibM becomes 1, 
29       fibMm2 becomes 0 */
30    while (fibM > 1) 
31    { 
32        // Check if fibMm2 is a valid location 
33        int i = min(offset+fibMMm2, n-1); 
34  
35        /* If x is greater than the value at index fibMm2, 
36           cut the subarray array from offset to i */
37        if (arr[i] < x) 
38        { 
39            fibM  = fibMMm1; 
40            fibMMm1 = fibMMm2; 
41            fibMMm2 = fibM - fibMMm1; 
42            offset = i; 
43        } 
44  
45        /* If x is greater than the value at index fibMm2, 
46           cut the subarray after i+1  */
47        else if (arr[i] > x) 
48        { 
49            fibM  = fibMMm2; 
50            fibMMm1 = fibMMm1 - fibMMm2; 
51            fibMMm2 = fibM - fibMMm1; 
52        } 
53  
54        /* element found. return index */
55        else return i; 
56    } 
57  
58    /* comparing the last element with x */
59    if(fibMMm1 && arr[offset+1]==x)return offset+1; 
60  
61    /*element not found. return -1 */
62    return -1; 
63} 
64  
65/* driver function */
66int main(void) 
67{ 
68    int arr[] = {10, 22, 35, 40, 45, 50, 80, 82, 
69                 85, 90, 100}; 
70    int n = sizeof(arr)/sizeof(arr[0]); 
71    int x = 85; 
72    printf("Found at index: %d", 
73            fibMonaccianSearch(arr, x, n)); 
74    return 0; 
75}

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

1// Java program for Fibonacci Search 
2import java.util.*; 
3  
4class Fibonacci 
5{    
6    // Utility function to find minimum  
7    // of two elements 
8    public static int min(int x, int y)  
9    { return (x <= y)? x : y; } 
10  
11    /* Returns index of x if present, else returns -1 */
12    public static int fibMonaccianSearch(int arr[],  
13                                         int x, int n) 
14    { 
15        /* Initialize fibonacci numbers */
16        int fibMMm2 = 0; // (m-2)'th Fibonacci No. 
17        int fibMMm1 = 1; // (m-1)'th Fibonacci No. 
18        int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci 
19  
20        /* fibM is going to store the smallest  
21        Fibonacci Number greater than or equal to n */
22        while (fibM < n) 
23        { 
24            fibMMm2 = fibMMm1; 
25            fibMMm1 = fibM; 
26            fibM = fibMMm2 + fibMMm1; 
27        } 
28  
29        // Marks the eliminated range from front 
30        int offset = -1; 
31  
32        /* while there are elements to be inspected.  
33        Note that we compare arr[fibMm2] with x.  
34        When fibM becomes 1, fibMm2 becomes 0 */
35        while (fibM > 1) 
36        { 
37            // Check if fibMm2 is a valid location 
38            int i = min(offset+fibMMm2, n-1); 
39  
40            /* If x is greater than the value at  
41            index fibMm2, cut the subarray array  
42            from offset to i */
43            if (arr[i] < x) 
44            { 
45                fibM = fibMMm1; 
46                fibMMm1 = fibMMm2; 
47                fibMMm2 = fibM - fibMMm1; 
48                offset = i; 
49            } 
50  
51            /* If x is greater than the value at index  
52            fibMm2, cut the subarray after i+1 */
53            else if (arr[i] > x) 
54            { 
55                fibM = fibMMm2; 
56                fibMMm1 = fibMMm1 - fibMMm2; 
57                fibMMm2 = fibM - fibMMm1; 
58            } 
59  
60            /* element found. return index */
61            else return i; 
62        } 
63  
64        /* comparing the last element with x */
65        if(fibMMm1 == 1 && arr[offset+1] == x) 
66            return offset+1; 
67  
68        /*element not found. return -1 */
69        return -1; 
70    } 
71      
72    // driver code 
73    public static void main(String[] args) 
74    { 
75        int arr[] = {10, 22, 35, 40, 45, 50,  
76                     80, 82, 85, 90, 100}; 
77        int n = 11; 
78        int x = 85; 
79        System.out.print ("Found at index: "+ 
80                   fibMonaccianSearch(arr, x, n)); 
81    } 
82} 
83  
84// This code is contributed by rishabh_jain

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

1# Python3 program for Fibonacci search. 
2from bisect import bisect_left 
3  
4# Returns index of x if present,  else  
5# returns -1  
6def fibMonaccianSearch(arr, x, n): 
7      
8    # Initialize fibonacci numbers  
9    fibMMm2 = 0 # (m-2)'th Fibonacci No. 
10    fibMMm1 = 1 # (m-1)'th Fibonacci No. 
11    fibM = fibMMm2 + fibMMm1 # m'th Fibonacci 
12  
13    # fibM is going to store the smallest  
14    # Fibonacci Number greater than or equal to n  
15    while (fibM < n): 
16        fibMMm2 = fibMMm1 
17        fibMMm1 = fibM 
18        fibM = fibMMm2 + fibMMm1 
19  
20    # Marks the eliminated range from front 
21    offset = -1; 
22  
23    # while there are elements to be inspected. 
24    # Note that we compare arr[fibMm2] with x. 
25    # When fibM becomes 1, fibMm2 becomes 0  
26    while (fibM > 1): 
27          
28        # Check if fibMm2 is a valid location 
29        i = min(offset+fibMMm2, n-1) 
30  
31        # If x is greater than the value at  
32        # index fibMm2, cut the subarray array  
33        # from offset to i  
34        if (arr[i] < x): 
35            fibM = fibMMm1 
36            fibMMm1 = fibMMm2 
37            fibMMm2 = fibM - fibMMm1 
38            offset = i 
39  
40        # If x is greater than the value at  
41        # index fibMm2, cut the subarray  
42        # after i+1 
43        elif (arr[i] > x): 
44            fibM = fibMMm2 
45            fibMMm1 = fibMMm1 - fibMMm2 
46            fibMMm2 = fibM - fibMMm1 
47  
48        # element found. return index  
49        else : 
50            return i 
51  
52    # comparing the last element with x */ 
53    if(fibMMm1 and arr[offset+1] == x): 
54        return offset+1; 
55  
56    # element not found. return -1  
57    return -1
58  
59# Driver Code 
60arr = [10, 22, 35, 40, 45, 50, 
61       80, 82, 85, 90, 100] 
62n = len(arr) 
63x = 85
64print("Found at index:", 
65      fibMonaccianSearch(arr, x, n)) 
66  
67# This code is contributed by rishabh_jain

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

1// C# program for Fibonacci Search 
2using System; 
3  
4class GFG { 
5      
6    // Utility function to find minimum  
7    // of two elements 
8    public static int min(int x, int y)  
9    { 
10        return (x <= y)? x : y;  
11    } 
12  
13    /* Returns index of x if present, else returns -1 */
14    public static int fibMonaccianSearch(int []arr,  
15                                        int x, int n) 
16    { 
17        /* Initialize fibonacci numbers */
18        int fibMMm2 = 0; // (m-2)'th Fibonacci No. 
19        int fibMMm1 = 1; // (m-1)'th Fibonacci No. 
20        int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci 
21  
22        /* fibM is going to store the smallest  
23        Fibonacci Number greater than or equal to n */
24        while (fibM < n) 
25        { 
26            fibMMm2 = fibMMm1; 
27            fibMMm1 = fibM; 
28            fibM = fibMMm2 + fibMMm1; 
29        } 
30  
31        // Marks the eliminated range from front 
32        int offset = -1; 
33  
34        /* while there are elements to be inspected.  
35        Note that we compare arr[fibMm2] with x.  
36        When fibM becomes 1, fibMm2 becomes 0 */
37        while (fibM > 1) 
38        { 
39            // Check if fibMm2 is a valid location 
40            int i = min(offset+fibMMm2, n-1); 
41  
42            /* If x is greater than the value at  
43            index fibMm2, cut the subarray array  
44            from offset to i */
45            if (arr[i] < x) 
46            { 
47                fibM = fibMMm1; 
48                fibMMm1 = fibMMm2; 
49                fibMMm2 = fibM - fibMMm1; 
50                offset = i; 
51            } 
52  
53            /* If x is greater than the value at index  
54            fibMm2, cut the subarray after i+1 */
55            else if (arr[i] > x) 
56            { 
57                fibM = fibMMm2; 
58                fibMMm1 = fibMMm1 - fibMMm2; 
59                fibMMm2 = fibM - fibMMm1; 
60            } 
61  
62            /* element found. return index */
63            else return i; 
64        } 
65  
66        /* comparing the last element with x */
67        if(fibMMm1 == 1 && arr[offset+1] == x) 
68            return offset + 1; 
69  
70        /*element not found. return -1 */
71        return -1; 
72    } 
73      
74    // driver code 
75    public static void Main() 
76    { 
77        int []arr = {10, 22, 35, 40, 45, 50,  
78                    80, 82, 85, 90, 100}; 
79        int n = 11; 
80        int x = 85; 
81        Console.Write ("Found at index: " + 
82                fibMonaccianSearch(arr, x, n)); 
83    } 
84} 
85  
86// This code is contributed by nitin mittal.

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

1<?php 
2// PHP program for Fibonacci Search 
3  
4/* Returns index of x if present, else returns -1 */
5function fibMonaccianSearch($arr, $x, $n) 
6{ 
7    /* Initialize fibonacci numbers */
8    $fibMMm2 = 0; // (m-2)'th Fibonacci No. 
9    $fibMMm1 = 1; // (m-1)'th Fibonacci No. 
10    $fibM = $fibMMm2 + $fibMMm1; // m'th Fibonacci 
11  
12    /* fibM is going to store the smallest Fibonacci 
13    Number greater than or equal to n */
14    while ($fibM < $n) 
15    { 
16        $fibMMm2 = $fibMMm1; 
17        $fibMMm1 = $fibM; 
18        $fibM = $fibMMm2 + $fibMMm1; 
19    } 
20  
21    // Marks the eliminated range from front 
22    $offset = -1; 
23  
24    /* while there are elements to be inspected. Note that 
25    we compare arr[fibMm2] with x. When fibM becomes 1, 
26    fibMm2 becomes 0 */
27    while ($fibM > 1) 
28    { 
29        // Check if fibMm2 is a valid location 
30        $i = min($offset+$fibMMm2, $n-1); 
31  
32        /* If x is greater than the value at index fibMm2, 
33        cut the subarray array from offset to i */
34        if ($arr[$i] < $x) 
35        { 
36            $fibM = $fibMMm1; 
37            $fibMMm1 = $fibMMm2; 
38            $fibMMm2 = $fibM - $fibMMm1; 
39            $offset = $i; 
40        } 
41  
42        /* If x is greater than the value at index fibMm2, 
43        cut the subarray after i+1 */
44        else if ($arr[$i] > $x) 
45        { 
46            $fibM = $fibMMm2; 
47            $fibMMm1 = $fibMMm1 - $fibMMm2; 
48            $fibMMm2 = $fibM - $fibMMm1; 
49        } 
50  
51        /* element found. return index */
52        else return $i; 
53    } 
54  
55    /* comparing the last element with x */
56    if($fibMMm1 && $arr[$offset + 1] == $x)return $offset+1; 
57  
58    /*element not found. return -1 */
59    return -1; 
60} 
61  
62/* driver code */
63    $arr = array(10, 22, 35, 40, 45, 50, 80, 82,85, 90, 100); 
64    $n = count($arr); 
65    $x = 85; 
66    printf("Found at index: ".fibMonaccianSearch($arr, $x, $n)); 
67  
68// This code is contributed by mits 
69?>

خروجی:

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
۱ دیدگاه برای «جستجوی فیبوناچی (Fibonacci Search) — به زبان ساده»

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

نظر شما چیست؟

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