c# - 在排序列表中搜索值时如何节省 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;
    }
}

测试结果为:

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

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

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

Answer 1

是的，我认为二分搜索 O(log(N)) 复杂度与 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

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