1.1.38

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

为了使差距比较明显,故意取了比较靠后的数字。

代码

static void Main(string[] args)
{
    string[] largeWString = File.ReadAllLines("largeW.txt");
    int[] largeW = new int[largeWString.Length];
    for (int i = 0; i < largeW.Length; ++i)
    {
        largeW[i] = int.Parse(largeWString[i]);
    }
    Stopwatch timer = Stopwatch.StartNew();
    BruteForceSearch(111111, largeW);
    Console.WriteLine($"BruteForceSearch: {timer.ElapsedMilliseconds} ms");

    timer.Restart();
    rank(111111, largeW);
    Console.WriteLine($"BinarySearch: {timer.ElapsedMilliseconds} ms");

    string[] largeTString = File.ReadAllLines("largeT.txt");
    int[] largeT = new int[largeTString.Length];
    for (int i = 0; i < largeW.Length; ++i)
    {
        largeT[i] = int.Parse(largeTString[i]);
    }

    timer.Restart();
    BruteForceSearch(111111, largeT);
    Console.WriteLine($"BruteForceSearch: {timer.ElapsedMilliseconds} ms");

    timer.Restart();
    rank(111111, largeT);
    Console.WriteLine($"BinarySearch: {timer.ElapsedMilliseconds} ms");
}

//暴力查找
public static int BruteForceSearch(int key, int[] a)
{
    for (int i = 0; i < a.Length; ++i)
    {
        if (a[i] == key)
            return i;
    }

    return -1;
}

//重载方法,用于启动二分查找
public static int rank(int key, int[] a)
{
    return rank(key, a, 0, a.Length - 1, 1);
}

//二分查找
public static int rank(int key, int[] a, int lo, int hi, int number)
{
    if (lo > hi)
    {
        return -1;
    }

    int mid = lo + (hi - lo) / 2;

    if (key < a[mid])
    {
        return rank(key, a, lo, mid - 1, number + 1);
    }
    else if (key > a[mid])
    {
        return rank(key, a, mid + 1, hi, number + 1);
    }
    else
    {
        return mid;
    }
}

另请参阅

LargeW.txt
LargeT.txt

上一题 下一题