在排序列表中搜索值时如何节省CPU周期? [英] How to save CPU cycles when searching for a value in a sorted list?

问题描述

在 CodinGame 学习平台中，在C#教程中用作示例的问题之一是:

In CodinGame learning platform, one of the questions used as an example in a C# tutorial is this one:

此练习的目的是检查数字中是否存在数字 数组.

The aim of this exercise is to check the presence of a number in an array.

规格:这些项目是按升序排列的整数. 该阵列最多可以包含一百万个项目.该数组从不null. 实现方法boolean Answer.Exists(int[] ints, int k)，以便 如果k属于ints，则返回true，否则该方法应 返回false.

Specifications: The items are integers arranged in ascending order. The array can contain up to 1 million items. The array is never null. Implement the method boolean Answer.Exists(int[] ints, int k) so that it returns true if k belongs to ints, otherwise the method should return false.

重要说明:如果可能，请尝试保存CPU周期.

Important note: Try to save CPU cycles if possible.

示例:

int[] ints = {-9, 14, 37, 102};

Answer.Exists(ints, 102)返回true.
Answer.Exists(ints, 36)返回false.

Answer.Exists(ints, 102) returns true.
Answer.Exists(ints, 36) returns false.

我的建议是这样做:

using System;
using System.IO;

public class Answer
{
    public static bool Exists(int[] ints, int k)
    {
        foreach (var i in ints)
        {
            if (i == k)
            {
                return true;
            }

            if (i > k)
            {
                return false;
            }
        }

        return false;
    }
}

测试结果为:

• ✔该解决方案适用于小型"阵列(200分)-问题解决
• ✔该解决方案适用于空数组(50分)-可靠性
• ✘该解决方案在合理的时间内可以处理一百万个项目(700分)-问题解决

我不明白最后一点.看来该代码可能比我建议的代码更优化.

I don't get the last point. It appears that the code may be more optimal than the one I suggested.

如何优化这段代码? 二进制搜索是一个实际的解决方案(假设数组中的值已经排序)，还是我错过了更简单的方法?

How to optimize this piece of code? Is a binary search an actual solution (given that the values in the array are already ordered), or there is something simpler that I missed?

推荐答案

这是有序数组的快速方法

public static class Answer
{
    public static bool Exists( int[] ints, int k )
    {
        var lower = 0;
        var upper = ints.Length - 1;

        if ( k < ints[lower] || k > ints[upper] ) return false;
        if ( k == ints[lower] ) return true;
        if ( k == ints[upper] ) return true;

        do
        {
            var middle = lower + ( upper - lower ) / 2;

            if ( ints[middle] == k ) return true;
            if ( lower == upper ) return false;

            if ( k < ints[middle] )
                upper = Math.Max( lower, middle - 1 );
            else
                lower = Math.Min( upper, middle + 1 );
        } while ( true );
    }
}

在我的cpu上花费约50个滴答(数组中有90.000.000个项目)

Takes around 50 ticks on my cpu (with 90.000.000 items in the array)

dotnetfiddle上的示例

这篇关于在排序列表中搜索值时如何节省CPU周期?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！