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

Question

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

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

规格：这些项目是按升序排列的整数。该阵列最多可包含一百万个项目。该数组从不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分）-可靠性
• ？该解决方案在合理的时间内可以处理一百万件商品（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/zh-CN/library/2cy9f6wb(v=vs.110).aspx

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