Binary search in C#

The challenge requires the program to receive data from the console and use binary search to find if a term is contained in a set of other terms. I've unit-tested the solution below, but according to the grader, my solution is too slow (i.e. the logic is "correct" but inefficient). The grader returns 30 seconds of execution time presumably for very large input (which I can't access).

Where's the bottleneck (or, how can I make this faster?)

The input consists of two lines:

• Input line 1 contains the number of data, followed by the actual data, already sorted.

Example: 5 1 5 8 12 13 represents a five-element list 1 5 8 12 13.

• Input line 2 contains the number of search terms, followed by the search terms.

Example: 5 8 1 23 1 11 represents five search terms: 8, 1, 23, 1, 11.

• Output for the example above: 2 0 -1 0 -1

Explanation: search term 8 is found at actual data location 2, 1 is found at 0, 23 is not found (returns -1), 1 is found at 0, 11 is not found (-1)

```
using System;
using System.Collections.Generic;
using System.Linq;

namespace BinarySearch
{
public class Program
{
public static void Main(string[] args)
{
new Launcher().Run(args);
}
}

public class Launcher
{
public void Run(string[] args)
{
var input = Console.ReadLine().Split(' ').Select(n => Convert.ToInt64(n)).ToArray();
var numData = (int)input[0];
// attempt to make console reading faster...
//var data = input.Skip(1).Take((int) (numData)).ToArray();
// attempt to make console reading faster...
//var data = new ArraySegment(input, 1, numData).ToArray();
var data = new List(input).GetRange(1, numData).ToArray();

var searchTerms = Console.ReadLine().Split(' ').Select(n => Convert.ToInt64(n)).ToArray();
var numSearchTerms = (int)searchTerms[0];
// attempt to make console reading faster...
//var search = searchTerms.Skip(1).Tak

If the number of search terms becomes large, it would be better to use a StringBuilder. Otherwise, a new string (which is growing) will be allocated for each iteration.

I would consider caching results:

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;

    var cache = new Dictionary();
    var resultBuilder = new StringBuilder();
    for (var i = 0; i < searchTerms.Length; i++)
    {
        var searchTerm = searchTerms[i];
        long result;
        if (!cache.TryGetValue(searchTerm, out result))
        {
            result = BinarySearch(data, lowerBound, upperBound, searchTerm);
            cache.Add(searchTerm, result);
        }
        resultBuilder.Append(result);
        resultBuilder.Append(" ");
    }
    return resultBuilder.ToString();
}

If you have a really large list and multiple cores, you also could try to parallelize the search, e.g. using Parallel.For in combination with a ConcurrentDictionary for caching:

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;

    var cache = new ConcurrentDictionary();
    var resultArray = new long[searchTerms.Length];
    Parallel.For(0, searchTerms.Length, i =>
    {
        var searchTerm = searchTerms[i];
        long result;
        if (!cache.TryGetValue(searchTerm, out result))
        {
            result = BinarySearch(data, lowerBound, upperBound, searchTerm);
            cache.TryAdd(searchTerm, result);
        }
        resultArray[i] = result;
    });
    return string.Join(" ", resultArray);
}

StackExchange Code Review Q#132972, answer score: 12