Binary Search – C# experiments

Back to experiments • This technical report was last updated on May 9, 2012 by Paul V. Borza
Paul V. Borza

Paul is a software engineer born in Transylvania who lives in the United States of America and works for Microsoft. About

The opinions and views expressed on this site are those of the author and do not necessarily state or reflect those of Microsoft.

Problem

Which of the three binary search implementations is faster?
One recursive and two different iterative implementations are compared, running on a list of sorted integers.

References

Test1Test2
OutcomeAverage (sec.)OutcomeAverage (sec.)
Variant1Passed0.000·046·128Passed1.003·991·821
Variant2Passed-11.34%0.000·040·895Passed-2.78%0.976·073·076
Variant3Passed-2.72%0.000·044·872Passed1.26%1.016·612·672

Interface

namespace BinarySearch
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics.Contracts;

    [ContractClass(typeof(BinarySearchContract))]
    public interface IBinarySearch
    {
        int BinarySearch<T>(IList<T> list, T searched) where T : IComparable;
    }

    [ContractClassFor(typeof(IBinarySearch))]
    internal abstract class BinarySearchContract : IBinarySearch
    {
        public int BinarySearch<T>(IList<T> list, T searched) where T : IComparable
        {
            Contract.Requires(null != list);
            Contract.Requires(list.Count > 0);
            Contract.Requires(null != searched);

            Contract.Ensures(Contract.Result<int>() >= -1 && Contract.Result<int>() < list.Count);

            return default(int);
        }
    }
}
.class interface public abstract auto ansi BinarySearch.IBinarySearch
{
  .method public hidebysig newslot abstract virtual 
          instance int32  BinarySearch<([mscorlib]System.IComparable) T>(class [mscorlib]System.Collections.Generic.IList`1<!!T> list,
                                                                         !!T searched) cil managed
  {
  } // end of method IBinarySearch::BinarySearch

} // end of class BinarySearch.IBinarySearch

Tests

namespace BinarySearch.Tests
{
    using System;
    using BinarySearch;
    using Microsoft.VisualStudio.TestTools.UnitTesting;

    public class Tests
    {
        public void Test1<T>() where T : IBinarySearch, new()
        {
            IBinarySearch variant = new T();

            Assert.AreEqual(-1, variant.BinarySearch(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 10));
        }

        public void Test2<T>() where T : IBinarySearch, new()
        {
            IBinarySearch variant = new T();

            var input = new int[1000000];

            var generate = new Random(2);
            for (var i = 0; i < input.Length; i++)
            {
                input[i] = generate.Next();
            }

            Array.Sort(input);

            Assert.AreEqual(123, variant.BinarySearch(input, input[123]));
        }
    }
}

Top

Variants

Variant1

BestWorstAverage
O(1)O(log(N))O(log(N))Time
O(1)O(1)O(1)Space

This is the well-known recursive version of the binary search algorithm.
However, due to its recursive nature, this algorithm also expects to run out of stack frames for huge arrays. If that happens, it will not throw a System.StackOverflowException; instead, it will recover by returning the middle value found so far, by leveraging the RuntimeHelpers.EnsureSufficientExecutionStack() function from the System.Runtime.CompilerServices namespace. Even though this is not ideal, it's a good way of returning an approximate result rather than exiting the application.
Also note that this recursive implementation uses tail recursion which doesn't create stack frames, so the chance of running out of stack space is very low.

This variant does not overflow when calculating the middle of the interval.
Note that middle=(low+high)/2 will overflow for large integers, but middle=low+((high-low)/2) will not.

References

namespace BinarySearch
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics.Contracts;
    using System.Runtime.CompilerServices;

    public sealed class Variant1 : IBinarySearch
    {
        public int BinarySearch<T>(IList<T> list, T searched) where T : IComparable
        {
            var result = this.BinarySearchHelper(list, searched, 0, list.Count - 1);

            return result;
        }

        private int BinarySearchHelper<T>(IList<T> list, T searched, int low, int high) where T : IComparable
        {
            // preconditions
            Contract.Requires(null != list);
            Contract.Requires(null != searched);

            if (low > high)
            {
                return -1;
            }

            // this calculation doesn't overflow
            var middle = checked(low + ((high - low) / 2));

            Contract.Assert(low <= middle && middle <= high);

            try
            {
                RuntimeHelpers.EnsureSufficientExecutionStack();
            }
            catch (InsufficientExecutionStackException)
            {
                // stack overflow is a corrupted state exception
                return middle; // it will run out of stack, so best is to return whatever we've got so far
            }

            Contract.Assert(middle >= 0 && middle < list.Count);

            switch (searched.CompareTo(list[middle]))
            {
                case +1:
                    return this.BinarySearchHelper(list, searched, middle + 1, high);
                case -1:
                    return this.BinarySearchHelper(list, searched, low, middle - 1);
                default:
                    return middle;
            }
        }
    }
}
.class public auto ansi sealed beforefieldinit BinarySearch.Variant1
       extends [mscorlib]System.Object
       implements BinarySearch.IBinarySearch
{
  .method public hidebysig newslot virtual final 
          instance int32  BinarySearch<([mscorlib]System.IComparable) T>(class [mscorlib]System.Collections.Generic.IList`1<!!T> list,
                                                                         !!T searched) cil managed
  {
    // Code size       233 (0xe9)
    .maxstack  13
    .locals init ([0] int32 result,
             [1] int32 CS$1$0000,
             [2] class [mscorlib]System.Collections.Generic.IList`1<!!T> 'Contract.Old(list)',
             [3] int32 'Contract.Result()')
//000030:             Contract.Requires(null != list);
    IL_0000:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
    IL_0005:  ldc.i4.4
    IL_0006:  bgt        IL_0069

    .try
    {
      IL_000b:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0010:  ldc.i4.1
      IL_0011:  add
      IL_0012:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0017:  ldnull
      IL_0018:  ldarg.1
      IL_0019:  ceq
      IL_001b:  ldc.i4.0
      IL_001c:  ceq
      IL_001e:  ldnull
      IL_001f:  ldstr      "null != list"
      IL_0024:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_0029:  nop
//000031:             Contract.Requires(list.Count > 0);
      IL_002a:  ldarg.1
      IL_002b:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
      IL_0030:  ldc.i4.0
      IL_0031:  cgt
      IL_0033:  ldnull
      IL_0034:  ldstr      "list.Count > 0"
      IL_0039:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_003e:  nop
//000032:             Contract.Requires(null != searched);
      IL_003f:  ldnull
      IL_0040:  ldarg.2
      IL_0041:  box        !!T
      IL_0046:  ceq
      IL_0048:  ldc.i4.0
      IL_0049:  ceq
      IL_004b:  ldnull
      IL_004c:  ldstr      "null != searched"
      IL_0051:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_0056:  nop
      IL_0057:  leave      IL_0069

    }  // end .try
    finally
    {
      IL_005c:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0061:  ldc.i4.1
      IL_0062:  sub
      IL_0063:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0068:  endfinally
    }  // end handler
    .try
    {
      IL_0069:  ldarg.1
      IL_006a:  stloc.2
      IL_006b:  leave      IL_007c

    }  // end .try
    catch [mscorlib]System.Exception 
    {
      IL_0070:  brtrue     IL_0077

      IL_0075:  rethrow
      IL_0077:  leave      IL_007c

//000035:         {
    }  // end handler
    IL_007c:  nop
//000036:             var result = this.BinarySearchHelper(list, searched, 0, list.Count - 1);
    IL_007d:  ldarg.0
    IL_007e:  ldarg.1
    IL_007f:  ldarg.2
    IL_0080:  ldc.i4.0
    IL_0081:  ldarg.1
    IL_0082:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_0087:  ldc.i4.1
    IL_0088:  sub.ovf
    IL_0089:  call       instance int32 BinarySearch.Variant1::BinarySearchHelper<!!0>(class [mscorlib]System.Collections.Generic.IList`1<!!0>,
                                                                                       !!0,
                                                                                       int32,
                                                                                       int32)
    IL_008e:  stloc.0
//000037: 
//000038:             return result;
    IL_008f:  ldloc.0
    IL_0090:  stloc.1
    IL_0091:  br         IL_0096

//000039:         }
    IL_0096:  ldloc.1
    IL_0097:  stloc.3
    IL_0098:  br         IL_009d

    IL_009d:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
    IL_00a2:  ldc.i4.4
    IL_00a3:  bgt        IL_00e7

    .try
    {
      IL_00a8:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_00ad:  ldc.i4.1
      IL_00ae:  add
      IL_00af:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
//000034:             Contract.Ensures(Contract.Result<int>() >= -1 && Contract.Result<int>() < list.Count);
      IL_00b4:  ldloc.3
      IL_00b5:  ldc.i4.m1
      IL_00b6:  blt        IL_00c9

      IL_00bb:  ldloc.3
      IL_00bc:  ldloc.2
      IL_00bd:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
      IL_00c2:  clt
      IL_00c4:  br         IL_00ca

      IL_00c9:  ldc.i4.0
      IL_00ca:  ldnull
      IL_00cb:  ldstr      "Contract.Result<int>() >= -1 && Contract.Result<in"
      + "t>() < list.Count"
      IL_00d0:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Ensures(bool,
                                                                                         string,
                                                                                         string)
      IL_00d5:  leave      IL_00e7

    }  // end .try
    finally
    {
      IL_00da:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_00df:  ldc.i4.1
      IL_00e0:  sub
      IL_00e1:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_00e6:  endfinally
    }  // end handler
    IL_00e7:  ldloc.3
    IL_00e8:  ret
  } // end of method Variant1::BinarySearch

  .method private hidebysig instance int32 
          BinarySearchHelper<([mscorlib]System.IComparable) T>(class [mscorlib]System.Collections.Generic.IList`1<!!T> list,
                                                               !!T searched,
                                                               int32 low,
                                                               int32 high) cil managed
  {
    // Code size       273 (0x111)
    .maxstack  14
    .locals init ([0] int32 middle,
             [1] int32 CS$1$0000,
             [2] bool CS$4$0001,
             [3] int32 CS$4$0002,
             [4] int32 'Contract.Result()')
//000044:             Contract.Requires(null != list);
    IL_0000:  ldnull
    IL_0001:  ldarg.1
    IL_0002:  ceq
    IL_0004:  ldc.i4.0
    IL_0005:  ceq
    IL_0007:  ldnull
    IL_0008:  ldstr      "null != list"
    IL_000d:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                        string,
                                                                                        string)
    IL_0012:  nop
//000045:             Contract.Requires(null != searched);
    IL_0013:  ldnull
    IL_0014:  ldarg.2
    IL_0015:  box        !!T
    IL_001a:  ceq
    IL_001c:  ldc.i4.0
    IL_001d:  ceq
    IL_001f:  ldnull
    IL_0020:  ldstr      "null != searched"
    IL_0025:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                        string,
                                                                                        string)
    IL_002a:  nop
//000042:         {
    IL_002b:  nop
//000043:             // preconditions
//000044:             Contract.Requires(null != list);
//000045:             Contract.Requires(null != searched);
//000046: 
//000047:             if (low > high)
    IL_002c:  ldarg.3
    IL_002d:  ldarg.s    high
    IL_002f:  cgt
    IL_0031:  ldc.i4.0
    IL_0032:  ceq
    IL_0034:  stloc.2
    IL_0035:  ldloc.2
    IL_0036:  brtrue     IL_0043

//000048:             {
    IL_003b:  nop
//000049:                 return -1;
    IL_003c:  ldc.i4.m1
    IL_003d:  stloc.1
    IL_003e:  br         IL_0105

//000050:             }
//000051: 
//000052:             // this calculation doesn't overflow
//000053:             var middle = checked(low + ((high - low) / 2));
    IL_0043:  ldarg.3
    IL_0044:  ldarg.s    high
    IL_0046:  ldarg.3
    IL_0047:  sub.ovf
    IL_0048:  ldc.i4.2
    IL_0049:  div
    IL_004a:  add.ovf
    IL_004b:  stloc.0
//000054: 
//000055:             Contract.Assert(low <= middle && middle <= high);
    IL_004c:  ldarg.3
    IL_004d:  ldloc.0
    IL_004e:  bgt        IL_0060

    IL_0053:  ldloc.0
    IL_0054:  ldarg.s    high
    IL_0056:  cgt
    IL_0058:  ldc.i4.0
    IL_0059:  ceq
    IL_005b:  br         IL_0061

    IL_0060:  ldc.i4.0
    IL_0061:  ldnull
    IL_0062:  ldstr      "low <= middle && middle <= high"
    IL_0067:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Assert(bool,
                                                                                      string,
                                                                                      string)
    IL_006c:  nop
//000056: 
//000057:             try
//000058:             {
    .try
    {
      IL_006d:  nop
//000059:                 RuntimeHelpers.EnsureSufficientExecutionStack();
      IL_006e:  call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::EnsureSufficientExecutionStack()
      IL_0073:  nop
//000060:             }
      IL_0074:  nop
      IL_0075:  leave      IL_0083

//000061:             catch (InsufficientExecutionStackException)
    }  // end .try
    catch [mscorlib]System.InsufficientExecutionStackException 
    {
      IL_007a:  pop
//000062:             {
      IL_007b:  nop
//000063:                 // stack overflow is a corrupted state exception
//000064:                 return middle; // it will run out of stack, so best is to return whatever we've got so far
      IL_007c:  ldloc.0
      IL_007d:  stloc.1
      IL_007e:  leave      IL_0105

    }  // end handler
    IL_0083:  nop
//000065:             }
//000066: 
//000067:             Contract.Assert(middle >= 0 && middle < list.Count);
    IL_0084:  ldloc.0
    IL_0085:  ldc.i4.0
    IL_0086:  blt        IL_0099

    IL_008b:  ldloc.0
    IL_008c:  ldarg.1
    IL_008d:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_0092:  clt
    IL_0094:  br         IL_009a

    IL_0099:  ldc.i4.0
    IL_009a:  ldnull
    IL_009b:  ldstr      "middle >= 0 && middle < list.Count"
    IL_00a0:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Assert(bool,
                                                                                      string,
                                                                                      string)
    IL_00a5:  nop
//000068: 
//000069:             switch (searched.CompareTo(list[middle]))
    IL_00a6:  ldarga.s   searched
    IL_00a8:  ldarg.1
    IL_00a9:  ldloc.0
    IL_00aa:  callvirt   instance !0 class [mscorlib]System.Collections.Generic.IList`1<!!T>::get_Item(int32)
    IL_00af:  box        !!T
    IL_00b4:  constrained. !!T
    IL_00ba:  callvirt   instance int32 [mscorlib]System.IComparable::CompareTo(object)
    IL_00bf:  stloc.3
    IL_00c0:  ldloc.3
    IL_00c1:  ldc.i4.m1
    IL_00c2:  sub
    IL_00c3:  switch     ( 
                          IL_00ec,
                          IL_00fe,
                          IL_00d9)
    IL_00d4:  br         IL_00fe

//000070:             {
//000071:                 case +1:
//000072:                     return this.BinarySearchHelper(list, searched, middle + 1, high);
    IL_00d9:  ldarg.0
    IL_00da:  ldarg.1
    IL_00db:  ldarg.2
    IL_00dc:  ldloc.0
    IL_00dd:  ldc.i4.1
    IL_00de:  add.ovf
    IL_00df:  ldarg.s    high
    IL_00e1:  call       instance int32 BinarySearch.Variant1::BinarySearchHelper<!!0>(class [mscorlib]System.Collections.Generic.IList`1<!!0>,
                                                                                       !!0,
                                                                                       int32,
                                                                                       int32)
    IL_00e6:  stloc.1
    IL_00e7:  br         IL_0105

//000073:                 case -1:
//000074:                     return this.BinarySearchHelper(list, searched, low, middle - 1);
    IL_00ec:  ldarg.0
    IL_00ed:  ldarg.1
    IL_00ee:  ldarg.2
    IL_00ef:  ldarg.3
    IL_00f0:  ldloc.0
    IL_00f1:  ldc.i4.1
    IL_00f2:  sub.ovf
    IL_00f3:  call       instance int32 BinarySearch.Variant1::BinarySearchHelper<!!0>(class [mscorlib]System.Collections.Generic.IList`1<!!0>,
                                                                                       !!0,
                                                                                       int32,
                                                                                       int32)
    IL_00f8:  stloc.1
    IL_00f9:  br         IL_0105

//000075:                 default:
//000076:                     return middle;
    IL_00fe:  ldloc.0
    IL_00ff:  stloc.1
    IL_0100:  br         IL_0105

    IL_0105:  nop
//000077:             }
//000078:         }
    IL_0106:  ldloc.1
    IL_0107:  stloc.s    'Contract.Result()'
    IL_0109:  br         IL_010e

    IL_010e:  ldloc.s    'Contract.Result()'
    IL_0110:  ret
  } // end of method Variant1::BinarySearchHelper

  .method public hidebysig specialname rtspecialname 
          instance void  .ctor() cil managed
  {
    // Code size       7 (0x7)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  call       instance void [mscorlib]System.Object::.ctor()
    IL_0006:  ret
  } // end of method Variant1::.ctor

} // end of class BinarySearch.Variant1
LinesBlocks
CoveredPartially coveredNot coveredCoveredNot covered
2323413
Coverage of Variant1 linesCoverage of Variant1 blocks

Top

Variant2

BestWorstAverage
O(1)O(log(N))O(log(N))Time
O(1)O(1)O(1)Space

This is the classic iterative variant of the binary search.
Comparing to the first implementation, this does not have the overhead of increasing the stack, which is much better.

The middle of the interval is computed in the same way as the first variant, which doesn't overflow.

References

namespace BinarySearch
{
    using System;
    using System.Collections.Generic;

    public sealed class Variant2 : IBinarySearch
    {
        public int BinarySearch<T>(IList<T> list, T searched) where T : IComparable
        {
            var low = 0;
            var middle = -1;
            var high = list.Count - 1;

            while (low <= high)
            {
                middle = checked(low + ((high - low) / 2));
                
                var result = searched.CompareTo(list[middle]);
                if (result > 0)
                {
                    low = middle + 1;
                }
                else if (result < 0)
                {
                    high = middle - 1;
                }
                else
                {
                    break;
                }
            }

            return low <= high ? middle : -1;
        }
    }
}
.class public auto ansi sealed beforefieldinit BinarySearch.Variant2
       extends [mscorlib]System.Object
       implements BinarySearch.IBinarySearch
{
  .method public hidebysig newslot virtual final 
          instance int32  BinarySearch<([mscorlib]System.IComparable) T>(class [mscorlib]System.Collections.Generic.IList`1<!!T> list,
                                                                         !!T searched) cil managed
  {
    // Code size       363 (0x16b)
    .maxstack  13
    .locals init ([0] int32 low,
             [1] int32 middle,
             [2] int32 high,
             [3] int32 result,
             [4] int32 CS$1$0000,
             [5] bool CS$4$0001,
             [6] class [mscorlib]System.Collections.Generic.IList`1<!!T> 'Contract.Old(list)',
             [7] int32 'Contract.Result()')
//000030:             Contract.Requires(null != list);
    IL_0000:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
    IL_0005:  ldc.i4.4
    IL_0006:  bgt        IL_0069

    .try
    {
      IL_000b:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0010:  ldc.i4.1
      IL_0011:  add
      IL_0012:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0017:  ldnull
      IL_0018:  ldarg.1
      IL_0019:  ceq
      IL_001b:  ldc.i4.0
      IL_001c:  ceq
      IL_001e:  ldnull
      IL_001f:  ldstr      "null != list"
      IL_0024:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_0029:  nop
//000031:             Contract.Requires(list.Count > 0);
      IL_002a:  ldarg.1
      IL_002b:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
      IL_0030:  ldc.i4.0
      IL_0031:  cgt
      IL_0033:  ldnull
      IL_0034:  ldstr      "list.Count > 0"
      IL_0039:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_003e:  nop
//000032:             Contract.Requires(null != searched);
      IL_003f:  ldnull
      IL_0040:  ldarg.2
      IL_0041:  box        !!T
      IL_0046:  ceq
      IL_0048:  ldc.i4.0
      IL_0049:  ceq
      IL_004b:  ldnull
      IL_004c:  ldstr      "null != searched"
      IL_0051:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_0056:  nop
      IL_0057:  leave      IL_0069

    }  // end .try
    finally
    {
      IL_005c:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0061:  ldc.i4.1
      IL_0062:  sub
      IL_0063:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0068:  endfinally
    }  // end handler
    .try
    {
      IL_0069:  ldarg.1
      IL_006a:  stloc.s    'Contract.Old(list)'
      IL_006c:  leave      IL_007d

    }  // end .try
    catch [mscorlib]System.Exception 
    {
      IL_0071:  brtrue     IL_0078

      IL_0076:  rethrow
      IL_0078:  leave      IL_007d

//000029:         {
    }  // end handler
    IL_007d:  nop
//000030:             var low = 0;
    IL_007e:  ldc.i4.0
    IL_007f:  stloc.0
//000031:             var middle = -1;
    IL_0080:  ldc.i4.m1
    IL_0081:  stloc.1
//000032:             var high = list.Count - 1;
    IL_0082:  ldarg.1
    IL_0083:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_0088:  ldc.i4.1
    IL_0089:  sub.ovf
    IL_008a:  stloc.2
    IL_008b:  br         IL_00f0

//000033: 
//000034:             while (low <= high)
//000035:             {
    IL_0090:  nop
//000036:                 middle = checked(low + ((high - low) / 2));
    IL_0091:  ldloc.0
    IL_0092:  ldloc.2
    IL_0093:  ldloc.0
    IL_0094:  sub.ovf
    IL_0095:  ldc.i4.2
    IL_0096:  div
    IL_0097:  add.ovf
    IL_0098:  stloc.1
//000037:                 
//000038:                 var result = searched.CompareTo(list[middle]);
    IL_0099:  ldarga.s   searched
    IL_009b:  ldarg.1
    IL_009c:  ldloc.1
    IL_009d:  callvirt   instance !0 class [mscorlib]System.Collections.Generic.IList`1<!!T>::get_Item(int32)
    IL_00a2:  box        !!T
    IL_00a7:  constrained. !!T
    IL_00ad:  callvirt   instance int32 [mscorlib]System.IComparable::CompareTo(object)
    IL_00b2:  stloc.3
//000039:                 if (result > 0)
    IL_00b3:  ldloc.3
    IL_00b4:  ldc.i4.0
    IL_00b5:  cgt
    IL_00b7:  ldc.i4.0
    IL_00b8:  ceq
    IL_00ba:  stloc.s    CS$4$0001
    IL_00bc:  ldloc.s    CS$4$0001
    IL_00be:  brtrue     IL_00ce

//000040:                 {
    IL_00c3:  nop
//000041:                     low = middle + 1;
    IL_00c4:  ldloc.1
    IL_00c5:  ldc.i4.1
    IL_00c6:  add.ovf
    IL_00c7:  stloc.0
//000042:                 }
    IL_00c8:  nop
    IL_00c9:  br         IL_00ef

//000043:                 else if (result < 0)
    IL_00ce:  ldloc.3
    IL_00cf:  ldc.i4.0
    IL_00d0:  clt
    IL_00d2:  ldc.i4.0
    IL_00d3:  ceq
    IL_00d5:  stloc.s    CS$4$0001
    IL_00d7:  ldloc.s    CS$4$0001
    IL_00d9:  brtrue     IL_00e9

//000044:                 {
    IL_00de:  nop
//000045:                     high = middle - 1;
    IL_00df:  ldloc.1
    IL_00e0:  ldc.i4.1
    IL_00e1:  sub.ovf
    IL_00e2:  stloc.2
//000046:                 }
    IL_00e3:  nop
    IL_00e4:  br         IL_00ef

//000047:                 else
//000048:                 {
    IL_00e9:  nop
//000049:                     break;
    IL_00ea:  br         IL_00fd

//000050:                 }
//000051:             }
    IL_00ef:  nop
//000034:             while (low <= high)
    IL_00f0:  ldloc.0
    IL_00f1:  ldloc.2
    IL_00f2:  cgt
    IL_00f4:  ldc.i4.0
    IL_00f5:  ceq
    IL_00f7:  stloc.s    CS$4$0001
    IL_00f9:  ldloc.s    CS$4$0001
    IL_00fb:  brtrue.s   IL_0090

//000035:             {
//000036:                 middle = checked(low + ((high - low) / 2));
//000037:                 
//000038:                 var result = searched.CompareTo(list[middle]);
//000039:                 if (result > 0)
//000040:                 {
//000041:                     low = middle + 1;
//000042:                 }
//000043:                 else if (result < 0)
//000044:                 {
//000045:                     high = middle - 1;
//000046:                 }
//000047:                 else
//000048:                 {
//000049:                     break;
//000050:                 }
//000051:             }
//000052: 
//000053:             return low <= high ? middle : -1;
    IL_00fd:  ldloc.0
    IL_00fe:  ldloc.2
    IL_00ff:  ble        IL_010a

    IL_0104:  ldc.i4.m1
    IL_0105:  br         IL_010b

    IL_010a:  ldloc.1
    IL_010b:  stloc.s    CS$1$0000
    IL_010d:  br         IL_0112

//000054:         }
    IL_0112:  ldloc.s    CS$1$0000
    IL_0114:  stloc.s    'Contract.Result()'
    IL_0116:  br         IL_011b

    IL_011b:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
    IL_0120:  ldc.i4.4
    IL_0121:  bgt        IL_0168

    .try
    {
      IL_0126:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_012b:  ldc.i4.1
      IL_012c:  add
      IL_012d:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
//000034:             Contract.Ensures(Contract.Result<int>() >= -1 && Contract.Result<int>() < list.Count);
      IL_0132:  ldloc.s    'Contract.Result()'
      IL_0134:  ldc.i4.m1
      IL_0135:  blt        IL_014a

      IL_013a:  ldloc.s    'Contract.Result()'
      IL_013c:  ldloc.s    'Contract.Old(list)'
      IL_013e:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
      IL_0143:  clt
      IL_0145:  br         IL_014b

      IL_014a:  ldc.i4.0
      IL_014b:  ldnull
      IL_014c:  ldstr      "Contract.Result<int>() >= -1 && Contract.Result<in"
      + "t>() < list.Count"
      IL_0151:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Ensures(bool,
                                                                                         string,
                                                                                         string)
      IL_0156:  leave      IL_0168

    }  // end .try
    finally
    {
      IL_015b:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0160:  ldc.i4.1
      IL_0161:  sub
      IL_0162:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0167:  endfinally
    }  // end handler
    IL_0168:  ldloc.s    'Contract.Result()'
    IL_016a:  ret
  } // end of method Variant2::BinarySearch

  .method public hidebysig specialname rtspecialname 
          instance void  .ctor() cil managed
  {
    // Code size       7 (0x7)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  call       instance void [mscorlib]System.Object::.ctor()
    IL_0006:  ret
  } // end of method Variant2::.ctor

} // end of class BinarySearch.Variant2
LinesBlocks
CoveredPartially coveredNot coveredCoveredNot covered
2100290
Coverage of Variant2 linesCoverage of Variant2 blocks

Top

Variant3

BestWorstAverage
O(1)O(log(N))O(log(N))Time
O(1)O(1)O(1)Space

This is a different iterative implementation which initially starts from the largest power of two that's less than the length of the list.
The second loop will decrease the step till it reaches 0, which is exactly log(N) times. At the same time, it shifts the offset to the right if the searched value is greater than the current one.
The last check determines whether to return -1 (for a value which wasn't found), or the actual index of the searched value in the array.

References

namespace BinarySearch
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics.Contracts;

    public sealed class Variant3 : IBinarySearch
    {
        public int BinarySearch<T>(IList<T> list, T searched) where T : IComparable
        {
            var step = 1;

            // calculates the first power of two which is greater than the length of the list
            while (step < list.Count)
            {
                // multiplies by two, equivalent to step *= 2
                step <<= 1;
            }

            Contract.Assert(step >= list.Count);

            // executes log(N) times, while increasing the offset, i, and decreasing the step
            var i = 0;
            for (i = 0; step > 0; step >>= 1)
            {
                if (i + step < list.Count && searched.CompareTo(list[i + step]) >= 0)
                {
                    i += step;
                }
            }

            Contract.Assume(i < list.Count);

            return 0 == searched.CompareTo(list[i]) ? i : -1;
        }
    }
}
.class public auto ansi sealed beforefieldinit BinarySearch.Variant3
       extends [mscorlib]System.Object
       implements BinarySearch.IBinarySearch
{
  .method public hidebysig newslot virtual final 
          instance int32  BinarySearch<([mscorlib]System.IComparable) T>(class [mscorlib]System.Collections.Generic.IList`1<!!T> list,
                                                                         !!T searched) cil managed
  {
    // Code size       414 (0x19e)
    .maxstack  20
    .locals init ([0] int32 step,
             [1] int32 i,
             [2] int32 CS$1$0000,
             [3] bool CS$4$0001,
             [4] class [mscorlib]System.Collections.Generic.IList`1<!!T> 'Contract.Old(list)',
             [5] int32 'Contract.Result()')
    .language '{3F5162F8-07C6-11D3-9053-00C04FA302A1}', '{994B45C4-E6E9-11D2-903F-00C04FA302A1}', '{5A869D0B-6611-11D3-BD2A-0000F80849BD}'
//000030:             Contract.Requires(null != list);
    IL_0000:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
    IL_0005:  ldc.i4.4
    IL_0006:  bgt        IL_0069

    .try
    {
      IL_000b:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0010:  ldc.i4.1
      IL_0011:  add
      IL_0012:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0017:  ldnull
      IL_0018:  ldarg.1
      IL_0019:  ceq
      IL_001b:  ldc.i4.0
      IL_001c:  ceq
      IL_001e:  ldnull
      IL_001f:  ldstr      "null != list"
      IL_0024:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_0029:  nop
//000031:             Contract.Requires(list.Count > 0);
      IL_002a:  ldarg.1
      IL_002b:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
      IL_0030:  ldc.i4.0
      IL_0031:  cgt
      IL_0033:  ldnull
      IL_0034:  ldstr      "list.Count > 0"
      IL_0039:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_003e:  nop
//000032:             Contract.Requires(null != searched);
      IL_003f:  ldnull
      IL_0040:  ldarg.2
      IL_0041:  box        !!T
      IL_0046:  ceq
      IL_0048:  ldc.i4.0
      IL_0049:  ceq
      IL_004b:  ldnull
      IL_004c:  ldstr      "null != searched"
      IL_0051:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Requires(bool,
                                                                                          string,
                                                                                          string)
      IL_0056:  nop
      IL_0057:  leave      IL_0069

    }  // end .try
    finally
    {
      IL_005c:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0061:  ldc.i4.1
      IL_0062:  sub
      IL_0063:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0068:  endfinally
    }  // end handler
    .try
    {
      IL_0069:  ldarg.1
      IL_006a:  stloc.s    'Contract.Old(list)'
      IL_006c:  leave      IL_007d

    }  // end .try
    catch [mscorlib]System.Exception 
    {
      IL_0071:  brtrue     IL_0078

      IL_0076:  rethrow
      IL_0078:  leave      IL_007d

//000030:         {
    }  // end handler
    IL_007d:  nop
//000031:             var step = 1;
    IL_007e:  ldc.i4.1
    IL_007f:  stloc.0
    IL_0080:  br         IL_008b

//000032: 
//000033:             // calculates the first power of two which is greater than the length of the list
//000034:             while (step < list.Count)
//000035:             {
    IL_0085:  nop
//000036:                 // multiplies by two, equivalent to step *= 2
//000037:                 step <<= 1;
    IL_0086:  ldloc.0
    IL_0087:  ldc.i4.1
    IL_0088:  shl
    IL_0089:  stloc.0
//000038:             }
    IL_008a:  nop
//000034:             while (step < list.Count)
    IL_008b:  ldloc.0
    IL_008c:  ldarg.1
    IL_008d:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_0092:  clt
    IL_0094:  stloc.3
    IL_0095:  ldloc.3
    IL_0096:  brtrue.s   IL_0085

//000035:             {
//000036:                 // multiplies by two, equivalent to step *= 2
//000037:                 step <<= 1;
//000038:             }
//000039: 
//000040:             Contract.Assert(step >= list.Count);
    IL_0098:  ldloc.0
    IL_0099:  ldarg.1
    IL_009a:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_009f:  clt
    IL_00a1:  ldc.i4.0
    IL_00a2:  ceq
    IL_00a4:  ldnull
    IL_00a5:  ldstr      "step >= list.Count"
    IL_00aa:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Assert(bool,
                                                                                      string,
                                                                                      string)
    IL_00af:  nop
//000041: 
//000042:             // executes log(N) times, while increasing the offset, i, and decreasing the step
//000043:             var i = 0;
    IL_00b0:  ldc.i4.0
    IL_00b1:  stloc.1
//000044:             for (i = 0; step > 0; step >>= 1)
    IL_00b2:  ldc.i4.0
    IL_00b3:  stloc.1
    IL_00b4:  br         IL_00fe

//000045:             {
    IL_00b9:  nop
//000046:                 if (i + step < list.Count && searched.CompareTo(list[i + step]) >= 0)
    IL_00ba:  ldloc.1
    IL_00bb:  ldloc.0
    IL_00bc:  add.ovf
    IL_00bd:  ldarg.1
    IL_00be:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_00c3:  bge        IL_00eb

    IL_00c8:  ldarga.s   searched
    IL_00ca:  ldarg.1
    IL_00cb:  ldloc.1
    IL_00cc:  ldloc.0
    IL_00cd:  add.ovf
    IL_00ce:  callvirt   instance !0 class [mscorlib]System.Collections.Generic.IList`1<!!T>::get_Item(int32)
    IL_00d3:  box        !!T
    IL_00d8:  constrained. !!T
    IL_00de:  callvirt   instance int32 [mscorlib]System.IComparable::CompareTo(object)
    IL_00e3:  ldc.i4.0
    IL_00e4:  clt
    IL_00e6:  br         IL_00ec

    IL_00eb:  ldc.i4.1
    IL_00ec:  stloc.3
    IL_00ed:  ldloc.3
    IL_00ee:  brtrue     IL_00f9

//000047:                 {
    IL_00f3:  nop
//000048:                     i += step;
    IL_00f4:  ldloc.1
    IL_00f5:  ldloc.0
    IL_00f6:  add.ovf
    IL_00f7:  stloc.1
//000049:                 }
    IL_00f8:  nop
//000050:             }
    IL_00f9:  nop
//000044:             for (i = 0; step > 0; step >>= 1)
    IL_00fa:  ldloc.0
    IL_00fb:  ldc.i4.1
    IL_00fc:  shr
    IL_00fd:  stloc.0
    IL_00fe:  ldloc.0
    IL_00ff:  ldc.i4.0
    IL_0100:  cgt
    IL_0102:  stloc.3
    IL_0103:  ldloc.3
    IL_0104:  brtrue.s   IL_00b9

//000045:             {
//000046:                 if (i + step < list.Count && searched.CompareTo(list[i + step]) >= 0)
//000047:                 {
//000048:                     i += step;
//000049:                 }
//000050:             }
//000051: 
//000052:             Contract.Assume(i < list.Count);
    IL_0106:  ldloc.1
    IL_0107:  ldarg.1
    IL_0108:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
    IL_010d:  clt
    IL_010f:  ldnull
    IL_0110:  ldstr      "i < list.Count"
    IL_0115:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Assume(bool,
                                                                                      string,
                                                                                      string)
    IL_011a:  nop
//000053: 
//000054:             return 0 == searched.CompareTo(list[i]) ? i : -1;
    IL_011b:  ldarga.s   searched
    IL_011d:  ldarg.1
    IL_011e:  ldloc.1
    IL_011f:  callvirt   instance !0 class [mscorlib]System.Collections.Generic.IList`1<!!T>::get_Item(int32)
    IL_0124:  box        !!T
    IL_0129:  constrained. !!T
    IL_012f:  callvirt   instance int32 [mscorlib]System.IComparable::CompareTo(object)
    IL_0134:  brfalse    IL_013f

    IL_0139:  ldc.i4.m1
    IL_013a:  br         IL_0140

    IL_013f:  ldloc.1
    IL_0140:  stloc.2
    IL_0141:  br         IL_0146

//000055:         }
    IL_0146:  ldloc.2
    IL_0147:  stloc.s    'Contract.Result()'
    IL_0149:  br         IL_014e

    IL_014e:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
    IL_0153:  ldc.i4.4
    IL_0154:  bgt        IL_019b

    .try
    {
      IL_0159:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_015e:  ldc.i4.1
      IL_015f:  add
      IL_0160:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
//000034:             Contract.Ensures(Contract.Result<int>() >= -1 && Contract.Result<int>() < list.Count);
      IL_0165:  ldloc.s    'Contract.Result()'
      IL_0167:  ldc.i4.m1
      IL_0168:  blt        IL_017d

      IL_016d:  ldloc.s    'Contract.Result()'
      IL_016f:  ldloc.s    'Contract.Old(list)'
      IL_0171:  callvirt   instance int32 class [mscorlib]System.Collections.Generic.ICollection`1<!!T>::get_Count()
      IL_0176:  clt
      IL_0178:  br         IL_017e

      IL_017d:  ldc.i4.0
      IL_017e:  ldnull
      IL_017f:  ldstr      "Contract.Result<int>() >= -1 && Contract.Result<in"
      + "t>() < list.Count"
      IL_0184:  call       void System.Diagnostics.Contracts.__ContractsRuntime::Ensures(bool,
                                                                                         string,
                                                                                         string)
      IL_0189:  leave      IL_019b

    }  // end .try
    finally
    {
      IL_018e:  ldsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_0193:  ldc.i4.1
      IL_0194:  sub
      IL_0195:  stsfld     int32 System.Diagnostics.Contracts.__ContractsRuntime::insideContractEvaluation
      IL_019a:  endfinally
    }  // end handler
    IL_019b:  ldloc.s    'Contract.Result()'
    IL_019d:  ret
  } // end of method Variant3::BinarySearch

  .method public hidebysig specialname rtspecialname 
          instance void  .ctor() cil managed
  {
    // Code size       7 (0x7)
    .maxstack  8
// Error reopening the file with FileToken 0x00000001
//000035: 
//000036:             return default(int);
//000037:         }
//000038:     }
//000039: }
    IL_0000:  ldarg.0
    IL_0001:  call       instance void [mscorlib]System.Object::.ctor()
    IL_0006:  ret
  } // end of method Variant3::.ctor

} // end of class BinarySearch.Variant3
LinesBlocks
CoveredPartially coveredNot coveredCoveredNot covered
1900390
Coverage of Variant3 linesCoverage of Variant3 blocks

Top

Comments