我正在尝试在我的程序中实现二进制搜索算法,但它似乎没有工作。
这是我的代码:
public static void Search(float[] array, float key)
{
int min = 0;
int max = array.Length - 1;
int mid = 0;
do
{
mid = (min + max) / 2;
if (key > array[mid])
{
min = mid + 1;
}
if (key < array[mid])
{
max = mid - 1;
}
if (key == array[mid])
Console.WriteLine($"The item, {key} was found at index {mid} of the array");
} while (min <= max);
(我正在使用的数组已排序)我只是得到一个空白的控制台,它似乎永远不会找到结果。我该怎么做才能解决它?
谢谢
更新:我已经从txt文件创建了float [],如下所示:
float[] floats = (File.ReadAllLines(@"floats.txt")).Where(s => s != String.Empty).Select(s => float.Parse(s)).ToArray();
Here's the contents of floats.txt (link to pastebin)
以下是用于测试算法是否有效的行:
Search(floats, -2.4439f);
(另外,我在尝试搜索之前对数组进行排序)
这段代码实际上适用于我,使用您提供的输入文件。我的猜测是你没有先排序数组:
static void Main(string[] args)
{
// Read in floats from input file
var lines = File.ReadAllLines(Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "input.txt"));
var floats = new List<float>();
foreach (var l in lines)
{
if (float.TryParse(l, out var result))
{
floats.Add(result);
}
}
var array = floats.OrderBy(f => f).ToArray();
float key = -2.4439f;
Search(array, key);
}
public static void Search(float[] array, float key)
{
int min = 0;
int max = array.Length - 1;
int mid = 0;
do
{
mid = (min + max) / 2;
if (key > array[mid])
{
min = mid + 1;
}
if (key < array[mid])
{
max = mid - 1;
}
Console.WriteLine($"Checking {array[mid]}");
if (key == array[mid])
{
Console.WriteLine($"The item, {key} was found at index {mid} of the array");
break;
}
} while (min <= max);
}
这是输出:
The item, -2.4439 was found at index 146 of the array
二进制搜索是递归函数的完美候选。也许你可以尝试这样的事情:
public static void Search(float[] array, float key, int? min = null, int? max = null)
{
if (!min.HasValue)
{
min = 0;
}
if (!max.HasValue)
{
max = array.Length - 1;
}
Console.WriteLine(string.Format("Searching from {0} to {1}", min.Value, max.Value));
if (min.Value >= max.Value)
{
if (array[min.Value] == key)
{
Console.WriteLine(string.Format("The item, {0} was found at index {1} of the array", key, min.Value));
}
}
else
{
int mid = (max.Value - min.Value) / 2;
if (mid < 1)
{
mid = 1;
}
Search(array, key, min, min.Value + mid - 1);
Search(array, key, min.Value + mid, max);
}
}