Fibonacci search algorithm throws Index out of range exception

I am trying to implement Fibonacci Search algorithm. But even after referring researching several resources I'm not able to figure it out.

The below function sometimes throws an index out of range exception. There must be some bug in my implementation, but I cannot find it.

public class Search
{
    public int FibonacciSearch(int[] arr, int x)
    {
        int n = arr.Length;
        int FibM2 = 0;
        int FibM1 = 1;
        int FibM = FibM1 + FibM2;

        while(FibM <= n)
        {
            FibM2 = FibM1;
            FibM1 = FibM;
            FibM = FibM1 + FibM2;
        }

        int offSet = -1;

        while (FibM2 > 0)
        {
            int index = Math.Min(offSet + FibM2, n - 1);
            if (arr[index] < x)
            {
                FibM = FibM1;
                FibM1 = FibM2;
                FibM2 = FibM - FibM1;
                offSet = index;
            }
            else if (arr[index] > x)
            {
                FibM = FibM2;
                FibM1 = FibM1 - FibM2;
                FibM2 = FibM - FibM1;
            }
            else
            {
                return index;
            }
        }

        if (FibM1 == 1 && arr[offSet + 1] == x)
            return (offSet + 1);

        return -1;
    }
}

Reproducing the error

When tried with some element present in the array, the Fibonacci search implementation seems to work.

But when I search some large number not present in the array, it throws error 'index out on range' in the last line:

        if (FibM1 == 1 && arr[offSet + 1] == x)

Here is driver code to reproduce that error:

Search _search = new Search();
int[] nums = { 1,2, 4, 5, 7, 44, 90, 121, 144 };
int position = _search.FibonacciSearch(nums, 145);

Solution

There are a few problems in your implementation:

The algorithm is intended to return a not-found condition once the main loop is exited without a match, but your implementation sometimes performs one more comparison arr[offSet + 1] == x. This is not intended to be there, and it is problematic as you haven't safeguarded against the situation where offSet + 1 is out of range. I suppose you introduced this if block in an attempt to fix wrong outputs, but those were caused by the two next points and should not be solved by adding this if block. Remove it.
The wrong index is taken for choosing the next candidate. It should use the middle Fibonacci number, but your code uses the least one. Correct the following code:
```
int index = Math.Min(offSet + FibM2, n - 1);
```
to:
```
int index = Math.Min(offSet + FibM1, n - 1);
```
In the case where arr[index] < x, you correctly update the offSet so to indicate that the search should continue at the right side of the current index, but the update to the Fibonacci values is wrong. In this scenario the Fibonacci numbers should move back with two steps, not one. It turns out you misplaced the updates of the Fibonacci variables: the ones you placed in the else block actually belong in the if block, and vice versa. So swap those statements.
The loop condition FibM2 > 0 is wrong. There can be a case that your Fibonacci variables FibM2, FibM1, Fib are 1, 1, 2 respectively and they are reduced with two steps to 1, 0, 1. This is weird, because the middle one is now 𝐹₀ and the first one makes no sense anymore. But because of the faulty loop condition your loop will continue to make iterations with these nonsensical values. Fix the loop condition to FibM > 1. This way the combination 1, 1, 2 will be allowed to make an iteration, but the combinations 0, 1, 1 (after one step reduction) or 1, 0, 1 (after two step reduction) will cause the loop to exit.

Here is your code with those corrections:

    public int FibonacciSearch(int[] arr, int x)
    {
        int n = arr.Length;
        int FibM2 = 0;
        int FibM1 = 1;
        int FibM = FibM1 + FibM2;

        while(FibM <= n)
        {
            FibM2 = FibM1;
            FibM1 = FibM;
            FibM = FibM1 + FibM2;
        }

        int offSet = -1;

        // Corrected loop check to allow for 1 1 2, but not 0 1 1 or less
        while (FibM > 1) 
        {
            // Corrected FibM2 to FibM1
            int index = Math.Min(offSet + FibM1, n - 1);
            if (arr[index] < x)
            {
                // Should reduce the Fibonacci numbers with TWO steps (swapped with next block)
                FibM = FibM2;
                FibM1 = FibM1 - FibM2;
                FibM2 = FibM - FibM1;
                offSet = index;
            }
            else if (arr[index] > x)
            {
                // Should reduce the Fibonacci numbers with ONE step (swapped with previous block)
                FibM = FibM1;
                FibM1 = FibM2;
                FibM2 = FibM - FibM1;
            }
            else
            {
                return index;
            }
        }
        // Removed problematic check. Once we get here the search failed.
        return -1;
    }