在排序列表中搜索值时如何节省 CPU 个循环？

Question

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

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

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.

Important note: Try to save CPU cycles if possible.

Example:
int[] ints = {-9, 14, 37, 102};
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;
    }
}

测试结果为：

✔ 该解决方案适用于 'small' 数组（200 点）- 问题解决
✔ 该解决方案适用于空数组（50 分）- 可靠性
✘ 该解决方案在合理的时间内适用于一百万项（700 分）- 问题解决

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

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

Answer 1

是的，我认为二分查找 O(log(N)) 复杂度 v. O(N) 复杂度是解决方案：

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

因为 Array.BinarySearch return 非负值 如果找到项目 (k) 则值：

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

Return Value Type: System.Int32 The index of the specified value in the specified array, if value is found; otherwise, a negative number.

Answer 2

是的，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 3

这是一个有序数组

的快速方法

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 4

如果您试图从中榨取每一盎司的速度...请考虑您的数组有 1..100 而您想要搜索 78。您的算法需要搜索并比较 78 个项目才能找到正确的那一个。如果您搜索第一项但它不存在，那么您跳转到数组大小 / 2 并找到 50 怎么样？现在您跳过了 50 次迭代。你知道 78 必须在数组的上半部分，所以你可以再次将它分成两半并跳到 75，等等。通过连续将数组分成两半，你做的迭代比你的蛮力方法少得多。

Answer 5

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 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);
                }
            }

        }

Answer 7

显然，任务打算我们使用 the default binary search method 而不是实现一个。我也有点惊讶它在第三次测试中的评估结果。 "解决方案使用标准库执行二进制搜索（迭代整数）"

这有点令人困惑，他们本可以在代码中提到这一点，而不是花 15 到 20 分钟来解决。这是造成这种混乱的另一个原因。

这就是我为那个问题写的 -> 将数组分成一半并搜索一半 -> 更基本的实现方式...

int half = size/2;
if( k < ints[half])
{
    for(int i=0; i < half; i++)
    {
        if( k == ints[i])
        {
             return true;
        }
    }
}
else
{
    for(int i=half; i < size; i++)
    {
        if( k == ints[i])
        {
            return true;
        }                
    }
 }

Answer 8

我看到了所有的解决方案，顺便说一句，我创建并测试了以下递归方法并获得了完整的要点：

public static bool Exists(int[] ints, int k)
    {


        if (ints.Length > 0 && ints[0] <= k && k <= ints[ints.Length - 1])
        {
            if (ints[0] == k || ints[ints.Length - 1] == k) return true;
            return SearchRecursive(ints, k, 0, ints.Length - 1) != -1;
        }
        return false;
    }

    private static int SearchRecursive(int[] array, int value, int first, int last)
    {
        int middle = (first + last) / 2;

        if (array[middle] == value)
        {
            return middle;
        }
        else if (first >= last)
        {
            return -1;
        }
        else if (value < array[middle])
        {
            return SearchRecursive(array, value, first, middle - 1);
        }
        else
        {
            return SearchRecursive(array, value, middle + 1, last);
        }
    }

在排序列表中搜索值时如何节省 CPU 个循环？

How to save CPU cycles when searching for a value in a sorted list?

c#

algorithm

optimization

binary-search