0

I have the following code which fetches a country ID based on the IP address:

countryID = GetAllCountryIPRanges().Single(c => c.BeginIPNum <= intIp && intIp <= c.EndIPNum).CountryID;

It's unfortunately quite slow as there's ~200,000 records. The ranges do not overlap, and GetAllCountryIPRanges() is in ascending order by BeginIPNum.

How do I implement .BinarySearch() on this list to find the correct record?

John Saunders
  • 160,644
  • 26
  • 247
  • 397
Tom Gullen
  • 61,249
  • 84
  • 283
  • 456
  • If you need a quick access to values maybe it's worth to consider a `Dictionary` instead of some `IEnumerable` collection. – PiotrWolkowski Nov 21 '14 at 17:25
  • Dictionary isn't suitable as we're searching on an imprecise value falling between stored ranges (see the working but slow example) – Tom Gullen Nov 21 '14 at 17:26
  • what if you keep ranges in a `Tuple` and used the `Tuple` as key? – PiotrWolkowski Nov 21 '14 at 17:30
  • What do you mean implement? There is a default implementation for List.BinarySearch(T item). You can use that right? – Piyush Parashar Nov 21 '14 at 17:34
  • In this case I would implement Binary Search myself. Since Binary Search is so easy to implement it seems like the quirks of implementing a comparer for use with the built in binary search are not worth it. – Stilgar Nov 21 '14 at 17:36
  • possible duplicate of [Doing a range lookup in C#?](http://stackoverflow.com/questions/454250/doing-a-range-lookup-in-c) – Erti-Chris Eelmaa Nov 21 '14 at 18:14
  • What do you mean by slow? Give us some reference. For some apps few seconds could be "slow" and for some others few ms could be "slow". – amit_g Nov 21 '14 at 18:55
  • O(N) vs O(log(N)) is quite a good reference for "slow" – Stilgar Nov 21 '14 at 20:39

2 Answers2

1

List has a binary search method but since binary search is so easy to implement and since the IComparator you would need to define is so complex due to the range thing I suggest you implement the binary search method

Something like this (NOT TESTED!)

public static IPRange BinarySearch(List<IPRange> source, int intIp)
{
    int startIndex = 0;
    int endIndex = source.Count;
    while (endIndex >= startIndex)
    {
        int middleIndex = startIndex + (endIndex - startIndex) / 2;
        if (source[middleIndex].BeginIPNum <= intIp && intIp <= source[middleIndex].EndIPNum)
        {
            return source[middleIndex];
        }
        else if (source[middleIndex].BeginIPNum < intIp)
        {
            startIndex = middleIndex + 1;
        }
        else
        {
            endIndex = middleIndex - 1;
        }
    }

    return null;
}

Assuming the List is sorted and there are no overlapping ranges.

Stilgar
  • 22,354
  • 14
  • 64
  • 101
  • "binary search is so easy to implement" - wait what :P? – Erti-Chris Eelmaa Nov 21 '14 at 18:09
  • Why is defining a Comparer complex? – Piyush Parashar Nov 21 '14 at 18:15
  • Because what he is searching for is actually a single number into a range. This means that he has to define equality as either one of the ranges being inside the other and that's only the equality. He needs to define less than as the end index of one being bigger than the start index of the other and the reverse for greater than. All this needs to reside in an inner class and implement the interface. Then he needs to create a Range object with both limits being the searched number and then he needs to call the built-in BS with that range and the comparer object. Implementing BS seems easier. – Stilgar Nov 21 '14 at 18:25
-1

Gotta love the elegance of recursion... (not tested)

public static IPRange BinarySearch(IList<IPRange> ipList, int ip)
{
   return BinarySearch(source, ip, 0, ipList.Count - 1);
}

public static IPRange BinarySearch(IList<IPRange> ipList, int ip, int min, int max)
{      
   if (min > max)
   {
     throw new Assertion("Error: ipList is empty, out-of-order, or does not contain an element that includes the IP");
   } 
   int mid = (min + max) / 2;
   var midIp = ipList[mid];
   if (ip < midIp.BeginIpNum)
   {
     return BinarySearch(ipList, ip, min, mid-1);
   }
   if (ip > midIp.EndIpNum)
   {
     return BinarySearch(ipList, ip, mid+1, max);
   }
   return midIp; 
}
Adam C
  • 20
  • 4