Binary search in non overlapping interval tree

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace GeneralTests
{
    internal class Program
    {
        public class RangeGroup
        {
            public uint RangeGroupId { get; set; }
            public uint Low { get; set; }
            public uint High { get; set; }
            // More properties related with the range here
        }

        public class RangeGroupFinder
        {
            private static readonly List<RangeGroup> RangeGroups = new List<RangeGroup>();

            static RangeGroupFinder()
            {
                uint prev = 1000000000 - 100;
                uint id = 0;
                for (uint i = 1000000000; i < uint.MaxValue; i += (uint)new Random().Next(500, 600))
                {
                    RangeGroups.Add(new RangeGroup { RangeGroupId = id, Low = prev + 1, High = i });
                    prev = i;
                    id++;
                    if (id == 5000000)
                    {
                        break;
                    }
                }
            }

            public static void Initialize()
            {

            }

            public static RangeGroup Find(uint number)
            {
                return RangeGroups.FirstOrDefault(rg => number >= rg.Low && number <= rg.High);
            }

            public static RangeGroup Find2(uint number)
            {
                int position = RangeGroups.Count / 2;
                int stepSize = position / 2;

                while (true)
                {
                    if (stepSize == 0)
                    {
                        // Couldn't find it.
                        return null;
                    }

                    if (RangeGroups[position].High < number)
                    {
                        // Search down.
                        position -= stepSize;

                    }
                    else if (RangeGroups[position].Low > number)
                    {
                        // Search up.
                        position += stepSize;

                    }
                    else
                    {
                        // Found it!
                        return RangeGroups[position];
                    }

                    stepSize /= 2;
                }
            }
        }

        private static bool CheckResult(RangeGroup rg, uint checkValue)
        {
            return checkValue >= rg.Low && checkValue <= rg.High;
        }

        private static void Main(string[] args)
        {
            var stopwatch = new Stopwatch();
            stopwatch.Start();
            RangeGroupFinder.Initialize();
            Console.WriteLine("Created the sample data in {0} ms.", stopwatch.ElapsedMilliseconds);

            double elapsedTicksLinq = 0;
            for (var i = 0; i < 16; i++)
            {
                var searchValue = (uint)(i * (uint.MaxValue / 16));
                Console.WriteLine("Searching for {0}", searchValue);
                stopwatch.Restart();
                var rg = RangeGroupFinder.Find(searchValue);
                elapsedTicksLinq += stopwatch.ElapsedTicks;
                if (rg != null && !CheckResult(rg, searchValue))
                {
                    throw new Exception(string.Format("Didn't check {0} in {1}-{2} ", i, rg.Low, rg.High));
                }
            }
            Console.WriteLine("Linq: {0} ticks.", elapsedTicksLinq);

            double elapsedTicksBinarySearch = 0;
            for (var i = 0; i < 16; i++)
            {
                var searchValue = (uint)(i * (uint.MaxValue / 16));
                Console.WriteLine("Searching for {0}", searchValue);
                stopwatch.Restart();
                var rg = RangeGroupFinder.Find2(searchValue);
                elapsedTicksBinarySearch += stopwatch.ElapsedTicks;
                if (rg != null && !CheckResult(rg, searchValue))
                {
                    throw new Exception(string.Format("Didn't check {0} in {1}-{2} ", i, rg.Low, rg.High));
                }
            }
            Console.WriteLine("BinarySearch: {0} ticks.", elapsedTicksBinarySearch);

            Console.WriteLine("BinarySearch is {0} times faster than Linq", elapsedTicksLinq / elapsedTicksBinarySearch);

            /* Results:
             * Created the sample data in 26255 ms.
             * Searching for 0
             * Searching for 268435455
             * Searching for 536870910
             * Searching for 805306365
             * Searching for 1073741820
             * Searching for 1342177275
             * Searching for 1610612730
             * Searching for 1879048185
             * Searching for 2147483640
             * Searching for 2415919095
             * Searching for 2684354550
             * Searching for 2952790005
             * Searching for 3221225460
             * Searching for 3489660915
             * Searching for 3758096370
             * Searching for 4026531825
             * Linq: 8230662 ticks.
             * Searching for 0
             * Searching for 268435455
             * Searching for 536870910
             * Searching for 805306365
             * Searching for 1073741820
             * Searching for 1342177275
             * Searching for 1610612730
             * Searching for 1879048185
             * Searching for 2147483640
             * Searching for 2415919095
             * Searching for 2684354550
             * Searching for 2952790005
             * Searching for 3221225460
             * Searching for 3489660915
             * Searching for 3758096370
             * Searching for 4026531825
             * BinarySearch: 1214 ticks.
             * BinarySearch is 6779.78747940692 times faster than Linq
             */

        }


    }
}