二进制搜索算法随机生成的数组项不起作用

Question

我已经在C#的控制台窗口应用程序中实现了二进制搜索算法。我正在为数组生成随机值，并分别使用Random()和Array.Sort()函数对它们进行排序。

问题-无论我给出什么（数组中要搜索的项目），当使用Random函数生成数组项目时，程序都会返回Key not found

如果我使用Console.ReadLine()手动输入数组元素，则不会发生这种情况。

TLDR:当手动输入数组项时，二进制搜索算法工作良好，但当使用Random函数生成数组项时不工作。

有人能指出我犯的错误是什么吗？

我的代码-随机生成的数组项

namespace BSA
{
  class Program
  {
    static void Main(string[] args)
    {
        var arr = new int[10];
        Random rnd = new Random();
        for (int i = 0; i < arr.Length; i++)
        {
            arr[i] = rnd.Next(1, 1000);
        }
        Array.Sort(arr);
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write("{0}n", i);
        }
        while (true)
        {
            Console.WriteLine("Enter the number to be searched in the array.");
            var searchItem = Convert.ToInt32(Console.ReadLine());
            var foundPos = Search(arr, searchItem);
            if (foundPos > 0)
            {
                Console.WriteLine("Key {0} found at position {1}", searchItem, foundPos);
            }
            else
            {
                Console.WriteLine("Key {0} not found", searchItem);
            }
        }
    }
    public static int Search(int[] arr, int item)
    {
        var min = 0;
        var N = arr.Length;
        var max = N - 1;
        int basicOperations = 0;
        basicOperations++;
        do
        {
            var mid = (min + max)/2;
            if (arr[mid] == item)
                return mid;
            if (item < arr[mid])
                max = mid - 1; 
            else
                min = mid + 1;
            basicOperations++;
        } while (min <= max);
        return basicOperations;
    }
  }
}

如果我在上面的代码中犯了任何愚蠢的错误或错误，请告诉我。任何帮助都会很有帮助。

Answer 1

据我所见，您的搜索代码运行良好。但是，当您列出随机数组的内容时，您应该写arr[i]而不是i来查看数组中的内容，这样您就可以在其中选择搜索值。或者，将arr[x]作为搜索项传递。它应该返回x。

Answer 2

您的代码工作正常。你只是找不到合适的钥匙。将生成的值打印到数组中的函数将打印循环计数器：

        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write("{0}n", i);
        }

您需要将其更改为：

        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write("{0}n", arr[i]);
        }

这将显示实际生成的值。

Answer 3

Comment太短，因此添加了答案来显示如何设置basicOperations并仍然返回搜索位置。您将basicOperations声明为out参数，这意味着方法可以更改它，以便调用方在方法返回时可以看到它。

public static void Main(string[] args)
{
    ... ... ...
    int basicOperations;
    int searchPos = IntArrayBinarySearch(arr, arr[5], out basicOperations);
    Console.WriteLine("Found at {0} basic ops={1}", searchPos, basicOperations);
}
public static int IntArrayBinarySearch(int[] data, int item, out int basicOperations)
{
    var min = 0;
    var N = data.Length;
    var max = N - 1;
    basicOperations = 0;
    basicOperations++;

在底部，您不需要返回out参数，只需像之前那样返回-1表示失败

    return -1;