Linear search vs. Binary search, C#

Linear search vs. Binary search

Language: Layout:

//http://stackoverflow.com/a/4870280/579026

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Collections.ObjectModel;
using System.Collections;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Random r = new Random();
            int max = Int32.MaxValue;
            
            List<TestClass> list = new List<TestClass>();
            for(int i=0; i<200000; i++)
                list.Add(new TestClass() {SomeValue = r.Next(0, max)});
                
            list.Add(new TestClass() {SomeValue = (int)max/2});
            
            list = list.OrderBy(f => f.SomeValue).ToList();
            
            for(int i=1; i<750; i++)
                Console.WriteLine(list.BinarySearch(new TestClass() {SomeValue = (int)max/2 }, new ValueComparer<TestClass>(f => f.SomeValue)));
            
            //now O(n) search time (compare the cpu times)
            //for(int i=1; i<750; i++)
                //Console.WriteLine(list.FirstOrDefault(f => f.SomeValue == (int)max/2).SomeValue);

}
        
        public class TestClass
        {
            public int SomeValue {get; set;}            
        }
    }
    
    //<summary>
    /// Contains all of the properties of a class that
    /// are used to provide value semantics.
    ///</summary>
    ///<remarks>
    /// You can create a static readonly ValueComparer for your class,
    /// then call into it from Equals, GetHashCode, and CompareTo.
    ///</remarks>
    class ValueComparer<T> : IComparer<T>, IEqualityComparer<T> 
    {
        public ValueComparer(params Func<T, object>[] props) 
        {
            Properties = new ReadOnlyCollection<Func<T, object>>(props);
        }
     
        public ReadOnlyCollection<Func<T, object>> Properties        
        { 
            get; 
            private set; 
        }
     
        public bool Equals(T x, T y) 
        {
            if (ReferenceEquals(x, y)) 
                return true;
            if (x == null || y == null) 
                return false;
            
            //Object.Equals handles strings and nulls correctly
            return Properties.All(f => Equals(f(x), f(y)));   
        }
     
        //http://stackoverflow.com/questions/263400/263416#263416
        public int GetHashCode(T obj) 
        {
            if (obj == null) return -42;
            unchecked 
            {
                int hash = 17;
                foreach (var prop in Properties) 
                {
                    object value = prop(obj);
                    if (value == null)
                        hash = hash * 23 - 1;
                    else
                        hash = hash * 23 + value.GetHashCode();
                }
                return hash;
            }
        }
     
        public int Compare(T x, T y) 
        {
            foreach (var prop in Properties) 
            {
                //The properties can be any type including null.
                var comp = Comparer.DefaultInvariant.Compare(prop(x), prop(y));   
                if (comp != 0)
                    return comp;
            }
            return 0;
        }
    }
}

Show compiler warnings [ + ] Show input
Compilation time: 0.37 sec, absolute running time: 0.31 sec, cpu time: 0.3 sec, average memory usage: 33 Mb, average nr of threads: 5

100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129 100129