c# - 为什么线性搜索不比二分搜索花费更多的时间？

Question

当我运行我的程序时，我加载了一个带有随机数的整数列表，我尝试过的最大值是 500000 个数字(加载需要几分钟)，然后我使用 listName.Sort 对列表进行排序();。

用户输入一个数字，我有一个“线性搜索”方法来检测列表是否包含该数字，如果是，我对每个列表数字进行 for 循环并尝试找到输入数字(线性/蛮力) .然后我打印数字输入和搜索结果之间的时间差(以毫秒为单位)。但我还有另一种二分搜索方法，它做同样的事情，但不是蛮力，而是进行二分搜索。

我一次尝试了两种搜索，希望二分搜索更快，但事实证明两者都需要 1 或 2 毫秒。我做错了什么，只花了这么少的时间？

static void Main(string[] args)
{
    List<int> arr = new List<int>();
    Random rnd = new Random();
    int randomNum;
    DateTime primeira = DateTime.Now;

//here i use 50000 numbers in the array
    for (var i = 0; i < 50000; i++)
    {
        do
        {
            //150000 options that don't repeat
            randomNum = rnd.Next(1, 150000);
        } while (arr.Contains(randomNum));
        arr.Add(randomNum);

    }
    arr.Sort();
    DateTime segunda = DateTime.Now;
    TimeSpan span = segunda - primeira;
    int ms = (int)span.TotalMilliseconds;
    Console.WriteLine($"Load time: {ms}");
    //I use this to know a number to search
    Console.WriteLine($"Biggest: {arr[arr.Count - 1]}"); 
    // search(arr);
    searchBrute(arr);  
}

public static void searchBrute(List<int> arr)
{
    Console.WriteLine("Insert a number for searching:");

    var input = Console.ReadLine();
    if (int.TryParse(input, out int number))
    {
        if (!arr.Contains(number))
        {
            Console.WriteLine("The number isn't in the array!");
            searchBrute(arr);
        }
        DateTime now = DateTime.Now;

        for (int i = 0; i < arr.Count; i++)
        {
            if(number == arr[i])
                showFound(number, i);
        }
        DateTime two = DateTime.Now;
        TimeSpan test = two - now;
        int msT = (int)test.TotalMilliseconds;
        Console.WriteLine($"Time taken: {msT}");
    }
}

public static void search(List<int> arr)
{
    bool found;
    int left = 0;
    int right = arr.Count - 1;
    Console.WriteLine("Insert a number for searching:");
    var input = Console.ReadLine();
    DateTime primeira = DateTime.Now;
    DateTime segunda;
    if (int.TryParse(input, out int number))
    {
        if (!arr.Contains(number))
        {
            Console.WriteLine("The number isn't in the array!");
            search(arr);
        }
        do
        {
            found = false;
            int mid = (left + right) / 2;
            if (number == arr[mid])
            {
                found = true;
                showFound(number, mid);

                segunda = DateTime.Now;
                TimeSpan span = segunda - primeira;
                int ms = (int)span.TotalMilliseconds;
                Console.WriteLine($"Time taken: {ms}");
            }
            else
            {
                if (arr[mid] > number)
                    right = mid - 1;
                else
                    left = mid + 1;

            }
        } while (!found);
    }
}

Answer 1

所以。正如其他人所说，在此计时使用 System.Diagnostics.Stopwatch。

这不是二分查找缓慢的原因。您的两种搜索方法都包含以下行:

if (!arr.Contains(number))

这是一个线性搜索。这可能使二分搜索看起来异常缓慢，因为它也是 O(n) 内部线性搜索。