代码并不总能找到索引。
我正尝试在 C# 中实现斐波那契搜索算法。有时算法找不到数组中的元素。我编写了单元测试来检查代码覆盖率,发现我的代码没有达到 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 扩展方法验证了该数字在数组中。
最佳答案
我用二进制搜索创建了一个小样本。使用 Fabonacci 搜索没有优势。您可以使用流阅读器一次添加一个整数,它们将同时添加和排序。
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;
}
关于c# - 如何修复代码以便 C# 中的斐波那契搜索算法正常工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54037466/