如何修复代码，使C#中的斐波那契搜索算法正常工作

Question

代码并不总是能找到索引。

我正在尝试在C#中实现fibonacci搜索算法。有时算法在数组中找不到元素。我写了单元测试来检查代码覆盖率，发现我的代码有10%没有达到。我还检查了其他实现。我认为问题出在这部分：

if (GetFibonacciNumberOnIndex(index - 1) == 1 && hayStack[offset + 1] == needle)
return offset + 1;

但从逻辑上讲，这应该在剩下最后一个元素时运行。

public static int FibSearch(int[] hayStack, int needle)
{
if (hayStack == null)
{
throw new ArgumentNullException(nameof(hayStack), "The array containing values to search in mustn't be null");
}
if (hayStack.Length == 0)
{
return -1;
}
int index = 0;
while (GetFibonacciNumberOnIndex(index) < hayStack.Length)
index++;
int offset = -1;
while (GetFibonacciNumberOnIndex(index) > 1)
{
int i = Math.Min(offset + GetFibonacciNumberOnIndex(index - 2), hayStack.Length - 1);
if (needle < hayStack[i])
index -= 2;
else if (needle > hayStack[i])
{
index--;
offset = i;
}
else
return i;               
}
if (GetFibonacciNumberOnIndex(index - 1) == needle && hayStack[offset + 1] == needle)
return offset + 1;
return -404;
}

private static int GetFibonacciNumberOnIndex(int index)
{
if (index < 1)
return 0;
else if (index == 1)
return 1;
int first = 0;
int second = 1;
int tmp = 0;
for (int i = 0; i < index; i++)
{
tmp = first;
first = second;
second = tmp + second;
}
return first;
}
}

我有一个档案，里面有1000000个号码。我正在读取文件并将内容转换为一个整数数组。最后，我搜索一个数字，知道这个数字在数组中，但算法返回-404。我在整数数组上使用Linq扩展方法验证了数字是否在数组中。

Answer 1

我用二进制搜索创建了一个小样本。使用Fabonacci搜索没有优势。您可以使用streamreader一次添加一个整数，它们将同时被添加和排序。

public class NumIndex:IComparable<NumIndex>
{
public int Number { get; set; }
public int Index { get; set; }
public int CompareTo(NumIndex other)
{
return this.Number.CompareTo(other.Number);
}
}
public static void Main(string[] args)
{
int[] nums = { 8, 4, 8, 1, 6, 3, 4, 32, 43, 5, 8, 95 };
List<NumIndex> intArray = new List<NumIndex>();
int i = 0;
foreach (int num in nums)
{
NumIndex newNum = new NumIndex() { Number = num, Index = i++ };
int index = intArray.BinarySearch(newNum);
if (index > -1)
{
//Item already found, you decide what to do with it, I added all numbers
}
else index = ~index;
intArray.Insert(index, newNum);
}
NumIndex dummy = new NumIndex() { Number = 18, Index = 0 };
int findItemIndex = intArray.BinarySearch(dummy);
if (findItemIndex < -1) throw new Exception("Item not found");
int itemIndex = intArray[].Index;
}