斐波那契搜索算法实现抛出索引越界异常，求问题排查

问题根源 #

当搜索的数值大于数组中所有元素时，循环结束后offSet会被设置为数组最后一个元素的索引（n-1），此时offSet + 1等于数组长度n，超出了数组的有效索引范围（数组索引最大为n-1），导致访问arr[offSet + 1]时抛出索引越界异常。

修复方案 #

在最后一行的判断逻辑中，先添加offSet + 1 < n的条件，确保索引合法后再进行元素比较。修改后的完整代码如下：

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 && offSet + 1 < n && arr[offSet + 1] == x)
            return (offSet + 1);

        return -1;
    }
}

补充说明 #

实际上在循环过程中，数组的最后一个元素已经通过Math.Min(offSet + FibM2, n - 1)被遍历过。当搜索值大于所有元素时，offSet最终会停在n-1，此时offSet +1必然超出数组范围，直接跳过该判断返回-1即可，不会遗漏任何有效匹配。

内容的提问来源于stack exchange，提问作者90CK