Revisions to Binary search in C#

fixed typos

Source Link

edit approved Jun 25, 2016 at 5:41

1

If the number of serach termessearch 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 to cachecaching 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 could also could try to parallelize the search, e.g. using Parallel.For in combination with ana CuncurrentDictionaryConcurrentDictionary 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);
}

If the number of serach termes 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 to cache 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 could also try to parallelize the search, e.g. using Parallel.For in combination with an CuncurrentDictionary 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);
}

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

restored accidentally removed content

Source Link

edited Jun 24, 2016 at 20:14

JanDotNet

8.5k
2
20
48

If the number of serach termes 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 to cache 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 could also try to parallelize the search, e.g. using Parallel.For in combination with an CuncurrentDictionary 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);
}

If the number of serach termes 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 to cache results:

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

If the number of serach termes 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 to cache 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 could also try to parallelize the search, e.g. using Parallel.For in combination with an CuncurrentDictionary 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);
}

fixed code

Source Link

edited Jun 24, 2016 at 19:58

JanDotNet

8.5k
2
20
48

If the number of serach termes 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 to cache 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 could also try to parallelize the search, e.g. using Parallel.For in combination with an CuncurrentDictionary for caching:

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

    var cache = new ConcurrentDictionary<long, long>();
    var resultBuilderresultArray = new StringBuilder();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);
        }
        resultBuilder.Append(result);
       resultArray[i] resultBuilder.Append("= ");result;
    });
    return resultBuilderstring.ToStringJoin(" ", resultArray);
}

If the number of serach termes 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 to cache 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 could also try to parallelize the search, e.g. using Parallel.For in combination with an CuncurrentDictionary for caching:

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

    var cache = new ConcurrentDictionary<long, long>();
    var resultBuilder = new StringBuilder();
    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);
        }
        resultBuilder.Append(result);
        resultBuilder.Append(" ");
    });
    return resultBuilder.ToString();
}

If the number of serach termes 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 to cache results:

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

added 763 characters in body

Source Link

edited Jun 24, 2016 at 19:14

JanDotNet

8.5k
2
20
48

Loading

Source Link

created Jun 24, 2016 at 19:04

JanDotNet

8.5k
2
20
48

Loading

Stack Exchange Network

Return to Answer