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

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

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

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.

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?>