Binary search in C#

Question

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<long>(input, 1, numData).ToArray();
        var data = new List<long>(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).Take((int)(numSearchTerms)).ToArray();
        // attempt to make console reading faster...
        //var search = new ArraySegment<long>(searchTerms, 1, numSearchTerms).ToArray();
        var search = new List<long>(searchTerms).GetRange(1, numSearchTerms).ToArray();

        Console.WriteLine(BinarySearchSetup(data, search));
    }

    public string BinarySearchSetup(long[] data, long[] searchTerms)
    {
        var resultString = "";

        var lowerBound = 0;
        var upperBound = data.Length - 1;

        for (var i = 0; i < searchTerms.Length; i++)
            resultString += BinarySearch(data, lowerBound, upperBound, searchTerms[i]) + " ";

        return resultString.Trim();
    }

    public long BinarySearch(long[] data, long low, long high, long key)
    {
        if (high < low)
            return -1;

        var mid = low + (high - low) / 2;

        if (key == data[mid])
            return mid;

        else if (key < data[mid])
            return BinarySearch(data, low, mid - 1, key);

        else
            return BinarySearch(data, mid + 1, high, key);
    }
}
}

Answer 1

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<long, long>();
    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<long, long>();
    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);
}

Answer 2

An alternative to using a StringBuilder is using LINQ with string.Join(). It's about as fast and is more concise and readable.

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var resultString = "";

    var lowerBound = 0;
    var upperBound = data.Length - 1;
    var results = searchTerms.Select(x => BinarySearch(data, lowerBound, upperBound, x));
    return string.Join(" ", results);
}

If you want to parallelize the operation, you can just call AsParallel() and then AsOrdered() to preserve order:

var results = searchTerms
    .AsParallel()
    .AsOrdered()
    .Select(x => BinarySearch(data, lowerBound, upperBound, x));

If you want to cache the results, you can build a dictionary on the distinct elements in a similar fashion to the above LINQ query. AsOrdered() is not required because it's getting stored in a dictionary. The method will look like this:

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;
    var cache = searchTerms
        .Distinct()
        .AsParallel()
        .ToDictionary(x => x, x => BinarySearch(data, lowerBound, upperBound, x));
    var results = searchTerms.Select(x => cache[x]);
    return string.Join(" ", results);
}

Edit: Regarding BinarySearch(), when I make recursive methods, I like to make a top level method with less parameters that calculates the extra parameters to pass into the recursive method. Like this:

public int BinarySearch(long[] data, long key)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;
    return BinarySearch(data, lowerBound, upperBound, key);
}

If you don't mind working with ints (which I think arrays are indexed with anyway), you can use Array.BinarySearch(). According to the documentation, a negative number is returned when an element is not found, and it's not necessarily -1, so we will have to handle that.

public int BinarySearch(long[] data, long key)
{
    int result = Array.BinarySearch(data, key);
    return Math.Max(result, -1); 
}

Answer 3

At first glance, resultString += is a first-class performance killer, speaking of string concatenation.

It's so frequent than there is a special class to overcome that : the StringBuilder class.

Usage is straightforward : stringBuilder.Append(string)

And when you really need the string : stringBuilder.ToString()

Hope this helps !