在排序列表中搜索值时如何节省CPU周期？

Question

在CodinGame学习平台中，在C＃教程中用作示例的问题之一是这一个：

本练习的目的是检查数组中是否存在数字。

规格：项目是按升序排列的整数。该阵列最多可包含100万个项目。阵列永远不会是null。实现方法boolean Answer.Exists(int[] ints, int k)，以便在true属于k时返回ints，否则该方法应返回false。

重要说明：尽可能尝试节省CPU周期。

例：

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

Answer.Exists(ints, 102)返回true。 Answer.Exists(ints, 36)返回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分） - 可靠性
• ✘解决方案在合理的时间内工作，有100万件（700分） - 解决问题

我没有得到最后一点。似乎代码可能比我建议的更优化。

如何优化这段代码？二进制搜索是一个实际的解决方案（假设数组中的值已经被排序），或者我错过了一些更简单的东西？

Answer 1

这是一个有序数组的快速方法

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个项目）

Sample on dotnetfiddle

Answer 2

是的，我认为二进制搜索O(log(N))复杂性v.O(N)复杂性是解决方案：

   public static bool Exists(int[] ints, int k) {
     return Array.BinarySearch(ints, k) >= 0;
   }

因为如果找到了项目（Array.BinarySearch），k会返回非负值：

https://msdn.microsoft.com/en-us/library/2cy9f6wb(v=vs.110).aspx

返回值类型：System.Int32指定数组中指定值的索引（如果找到值）;否则，为负数。

Answer 3

class Answer
{
    public static bool Exists(int[] ints, int k)
    {
        int index = Array.BinarySearch(ints, k);
        if (index > -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    static void Main(string[] args)
    {
        int[] ints = { -9, 14, 37, 102 };
        Console.WriteLine(Answer.Exists(ints, 14)); // true
        Console.WriteLine(Answer.Exists(ints, 4)); // false
    }

}

Answer 4

是的，BinarySearch比你手动编写的大多数算法都要快。但是，如果练习的目的是学习如何编写算法，那么您就走在了正确的轨道上。但是，你的算法会对if (i > k)进行不必要的检查......为什么你需要这个？

以下是我对此类简单要求的一般算法。像这样的while循环比for-loop稍微更高效，并且很容易执行foreach。

public class Answer
{
    public static bool Exists(int[] ints, int k)
    {
        var i = 0;
        var hasValue = false;

        while(i < ints.Length && !hasValue)
        {
            hasValue = ints[i] == k;
            ++i;
        }

        return hasValue;
    }
}

Answer 5

如果你试图挤出它的每一盎司速度...考虑你的阵列有1..100你想要搜索78.你的算法需要搜索并比较78项，然后才能找到合适的。相反，如果您搜索第一个项目而不是那里，那么您跳转到数组大小/ 2并找到50？现在你跳过了50次迭代。你知道78必须在数组的上半部分，所以你可以再将它分成两半并跳到75，等等。通过不断地将数组分成两半，你可以做更少的迭代，然后你的蛮力接近。

Answer 6

 public static bool Exists(int[] ints, int k)
        {
            var d = 0;
            var f = ints.Length - 1;
            if (d > f) return false;
            if (k > ints[f] || k < ints[d]) return false;
            if (k == ints[f] || k == ints[d]) return true;
            return (BinarySearch(ints, k, d, f) > 0);
        }

 public static int BinarySearch(int[] V, int Key, int begin, int end)
        {
            if (begin > end)
                return -1;
            var MidellIndex = (begin + end) / 2;

            if (Key == V[MidellIndex])
                return MidellIndex;
            else
            {
                if (Key > V[MidellIndex])
                {
                    begin = MidellIndex + 1;
                    return BinarySearch(V, Key, begin, end);
                }
                else
                {
                    end = MidellIndex - 1;
                    return BinarySearch(V, Key, begin, end);
                }
            }

        }