Back to basics – Part o..of..n-1 – Binary Search Algorithm Explained using C#

This is a brand new (and “sporadic”) series where I’ll try to cover basics of computer science/engineering, like algorithms, data-structures, design-patterns, scrum, agile process etc., etc.. Today, I’ll be discussing about Binary Search algorithm, why I started right away with it. I don’t know, you tell me. : ), You know what, actually its one of my favorite : ) .[digg]

Binary search is one of the very efficient algorithms when it comes to search an ordered collection. It is based on divide and conquer algorithm. That is the data is filtered in terms of dividing into halves and further halves, the process keeps on, until we are exhausted or we find the required key/data-item. This is achieved very easily using Recursion, that is being employed in most the cases. I also explained, in the end of the post, the iterative approach to implement Binary Search .

Lets take a look at the following figure (Figure-1). We have 18 data members of integers stored in a sorted array list. We are looking for a key = 11 and If you take a closer look at it, took only 4 probes/searches to get to the result. And it would be almost the same for almost all the cases, like if we are looking for 55. If it’s a linear search it will take 15 iterations to reach 55 while in case of binary search its again just 4 iterations. The search on the average takes O(logN) probes.

 
Figure-1

Let do some coding. I have created a static Test class, namely BinarySearchTests, instead of using built-in VS201 unit test framework, or third party NUnit or so, why?? good question lets move on, by the way just to keep things simple : ) This class unit-tests the static BinarySearchExt, that actually exposes Extension Methods for List<T> and uses IntComparer for sorting of the List<int> during testing. Here is the overall class diagram for our Binary Search Recursive system. What happens here, the BinarySearchTests is a static class that has bunch of Test methods, like Test1, Test2.. so on. And they all are called via Run-Tests, and assertion failure may occur when any one of them fails.

Figure-2

As I explained earlier the BinarySearchTests injects IntComparer object, where needed while testing BinarySearchExt. Here is the listing for it. Nothing so special going on, it actually has to implement IComparer<int>, that means you have to provide implementation for  Compare method. As you can see, what it does, if two integers are equal returns 0, otherwise if left-value (x)  integer is greater than the right-value (y) returns 1 or otherwise return –1. Static method, Comparison, is also equivalent to the Compare method and is used in the tests for sorting, just to show you the different ways of injecting of strategy of comparing elements while sorting elements in the List<T>. Another point, Separation Of Concerns, what that means? Well, it means data storage/structure is separated from business logic, like how the sorting can be done, or what would be the strategy of sorting would be injected on demand (The strategy design pattern), I’ll come to this pattern in a different post.

   1: using System;
   2: using System.Collections.Generic;
   3:  
   4: /// <summary>
   5: /// Provides Comparer for list of intigers
   6: /// </summary>
   7: class IntComparer : IComparer<int>
   8: {
   9:     public static int Comparison(int x, int y)
  10:     {
  11:         if (x > y) return 1;
  12:         if (x < y) return -1;
  13:  
  14:         //if (x == y) return 0;
  15:         return 0;
  16:     }
  17:  
  18:     public int Compare(int x, int y)
  19:     {
  20:         if (x > y) return 1;
  21:         if (x < y) return -1;
  22:  
  23:         //if (x == y) return 0;
  24:         return 0;
  25:     }
  26: }

Figure-3

And here is the implementation of BinarySearchTests. As you can see on line#7, the comparer is created, that are used in different tests. Take a look at Test1(), line 32 creates the list with some integer data, and then sorted at line 38, by injecting of the strategy or IComparer<int> to the sort method. Underneath the sort  method will use this IComparer for sorting purpose. Now take a look at line 41. That actually is calling an extension method, listInts.BinSearch3(11, comparer);  Will take a look at the BinSearch3 a little later. But just to clarify my point, in the BinSearh3 extension method, Custom Comparing Strategy is injected that  is of type IComparer.

   1: using System;
   2: using System.Collections.Generic;
   3: using System.Diagnostics;
   4:  
   5: public static class BinarySearchTests
   6: {
   7:     private static IntComparer comparer = new IntComparer();
   8:     
   9:     public static void RunTests()
  10:     {
  11:         Test1();
  12:         Test2();
  13:         Test3();
  14:         Test4();
  15:         Test5();
  16:         Test6();
  17:  
  18:         /* The output is
  19:          *  Test1.BinSearch3 | Passed | result index: 6
  20:             Test2.BinSearch2 | Passed | result index: 6
  21:             Test3.BinSearch | Passed | result index: 6
  22:             Test4.BinSearch | Passed | result index: 6
  23:             Test5.BinSearchX | Passed | result index: 6
  24:             Test6.BinarySearch | Passed | result index: 6
  25:          */
  26:     }
  27:  
  28:     /// <summary>
  29:     /// Test Search using extension method BinSearch3 defined in BinarySearchExt 
  30:     /// using the IntComparer
  31:     /// </summary>
  32:     public static void Test1()
  33:     {
  34:         List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
  35:  
  36:         //     Sorts the elements in the entire System.Collections.Generic.List<T> using
  37:         //     the specified comparer.
  38:         listInts.Sort(comparer);
  39:         // Sorted list is:
  40:         // 0 1 3 5 7 9 11 13 15 17 19 21 33 44 55 66 77 88
  41:  
  42:         // Search using extension method BinSearch3 defined in BinarySearchExt, using IntComparer
  43:         int index = listInts.BinSearch3(11, comparer);
  44:  
  45:         Debug.Assert(index == 6);
  46:  
  47:         Debug.WriteLine("Test1.BinSearch3 | Passed | result index: " + index);
  48:     }
  49:  
  50:     /// <summary>
  51:     /// Test Search using extension method BinSearch2 defined in BinarySearchExt
  52:     /// using the IntComparer.Comparison
  53:     /// </summary>
  54:     public static void Test2()
  55:     {
  56:         List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
  57:  
  58:         // using public delegate int Comparison<in T>(T x, T y); 
  59:         listInts.Sort(IntComparer.Comparison);
  60:         // Sorted list is:
  61:         // 0 1 3 5 7 9 11 13 15 17 19 21 33 44 55 66 77 88
  62:  
  63:         // Search using extension method BinSearch2 defined in BinarySearchExt
  64:         int index = listInts.BinSearch2(11);
  65:  
  66:         Debug.Assert(index == 6);
  67:  
  68:         Debug.WriteLine("Test2.BinSearch2 | Passed | result index: " + index);
  69:     }
  70:  
  71:     /// <summary>
  72:     /// Test Search using extension method BinSearch defined in BinarySearchExt
  73:     /// using the default  Comparison<int> delegate
  74:     /// </summary>
  75:     public static void Test3()
  76:     {
  77:         List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
  78:  
  79:         // Functional approach, lambda expressions.
  80:         Comparison<int> ComparisonDelegate = (int x, int y) =>
  81:         {
  82:             if (x > y) return 1;
  83:             if (x < y) return -1;
  84:  
  85:             //if (x == y) return 0;
  86:             return 0;
  87:         };
  88:  
  89:         // Sorts the elements in the entire System.Collections.Generic.List<T> using
  90:         // the specified System.Comparison<T> Delegate.
  91:         listInts.Sort(ComparisonDelegate);
  92:         // Sorted list is:
  93:         // 0 1 3 5 7 9 11 13 15 17 19 21 33 44 55 66 77 88
  94:  
  95:         // Search using extension method BinSearch defined in BinarySearchExt
  96:         int index = listInts.BinSearch(11);
  97:  
  98:         Debug.Assert(index == 6);
  99:  
 100:         Debug.WriteLine("Test3.BinSearch | Passed | result index: " + index);
 101:     }
 102:  
 103:     /// <summary>
 104:     /// Test Search using extension method BinSearch defined in BinarySearchExt
 105:     /// using the lambda expression Comparison<T> delegate
 106:     /// </summary>
 107:     public static void Test4()
 108:     {
 109:         List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
 110:  
 111:         // Sorts the elements in the entire System.Collections.Generic.List<T> using
 112:         // direct lambda expression Delegate.
 113:         listInts.Sort((int x, int y) =>
 114:         {
 115:             if (x > y) return 1;
 116:             if (x < y) return -1;
 117:  
 118:             //if (x == y) return 0;
 119:             return 0;
 120:         });
 121:  
 122:         // Sorted list is:
 123:         // 0 1 3 5 7 9 11 13 15 17 19 21 33 44 55 66 77 88
 124:  
 125:         // Search using extension method BinSearch defined in BinarySearchExt
 126:         int index = listInts.BinSearch(88);
 127:  
 128:         Debug.Assert(index == 17);
 129:  
 130:         Debug.WriteLine("Test4.BinSearch | Passed | result index: " + index);
 131:     }
 132:  
 133:     /// <summary>
 134:     /// Test Search using extension method BinSearchX defined in BinarySearchExt
 135:     /// </summary>
 136:     public static void Test5()
 137:     {
 138:         List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
 139:  
 140:         // The List<T> must already be sorted according to the comparer implementation; otherwise, the result is incorrect.
 141:         listInts.Sort();
 142:  
 143:         // Sorted list is:
 144:         // 0 1 3 5 7 9 11 13 15 17 19 21 33 44 55 66 77 88
 145:  
 146:         // Search using extension method BinSearchX defined in BinarySearchExt
 147:         int index = listInts.BinSearchX(11);
 148:  
 149:         Debug.Assert(index == 6);
 150:  
 151:         Debug.WriteLine("Test5.BinSearchX | Passed | result index: " + index);
 152:     }
 153:  
 154:     /// <summary>
 155:     /// Test using built-in BinarySearch defined in List<T>
 156:     /// using the default comparer
 157:     /// </summary>
 158:     public static void Test6()
 159:     {
 160:         List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
 161:  
 162:         // The List<T> must already be sorted according to the comparer implementation; otherwise, the result is incorrect.
 163:         listInts.Sort();
 164:  
 165:         // Search using built-in BinarySearch defined in List<T>
 166:         //   Searches the entire sorted System.Collections.Generic.List<T> for an element
 167:         //   using the default comparer and returns the zero-based index of the element.
 168:         int index = listInts.BinarySearch(11);
 169:  
 170:         Debug.Assert(index == 6);
 171:  
 172:         Debug.WriteLine("Test6.BinarySearch | Passed | result index: " + index);
 173:     }
 174: }

Figure-4

Now lets move on to static class BinarySearchExt, that actually contains all the extension methods, for Binary search against an array list, List<T>. All the techniques for this algorithm proposed are Recursive ones. The only difference among them is how you represent them using non-functional approach to pure function ones. Take a look at the following Figure-5. First one is Recursive one only (For code see Figure-6 below), Second one is functional but has some flaws, while last one pure-functional one.

Figure-5

Here is the implementation of Binary Search algorithm in C#. So what's exactly the algorithm. The algorithm is pretty simple, thanks to recursion and it is always great in divide and conquer algorithms or where you see a pattern exist on atomic level. Here you go:

Recursive Method
* Divide the data in two halves
* Search right (upper) half.
* Search left half (lower) half
* Until you find the element
* or you end-up with –1.

If you don’t provide a comparison strategy then the BinSearch? uses the default strategy. Take a look at line#14 below.

   1: using System;
   2: using System.Collections.Generic;
   3: using System.Diagnostics;
   4:  
   5: /// <summary>
   6: /// Extension methods for binary search
   7: /// </summary>
   8: public static class BinarySearchExt
   9: {
  10:     #region Recursive only approach
  11:  
  12:     public static int BinSearch3<T>(this List<T> list, T key, bool sortRequired = false)
  13:     {
  14:         Comparer<T> comparer = Comparer<T>.Default;
  15:  
  16:         return BinSearch3<T>(list, key, comparer, sortRequired);
  17:     }
  18:  
  19:     public static int BinSearch3<T>(this List<T> list, T key, IComparer<T> comparer, bool sortRequired = false)
  20:     {
  21:         if (sortRequired)
  22:         {
  23:             list.Sort(comparer);
  24:         }
  25:  
  26:         // Invoked with the initial low and high values of 0 and N-1.
  27:         return BinarySearchHelper<T>(list, comparer, key, 0, list.Count - 1);
  28:     }
  29:  
  30:     /// <summary>
  31:     ///  Binary search finds item in sorted ArrayList, Recursive method.
  32:     /// </summary>
  33:     /// <typeparam name="T"></typeparam>
  34:     /// <param name="list"></param>
  35:     /// <param name="comparer"></param>
  36:     /// <param name="key"></param>
  37:     /// <param name="lowerBound"></param>
  38:     /// <param name="upperBound"></param>
  39:     /// <returns></returns>
  40:     private static int BinarySearchHelper<T>(List<T> list,
  41:         IComparer<T> comparer,
  42:         T key,
  43:         int lowerBound,
  44:         int upperBound)
  45:     {
  46:         // check bounds
  47:         if (lowerBound > upperBound || lowerBound < 0)
  48:         {
  49:             return -1;  // return not found
  50:         }
  51:  
  52:         // the middle index
  53:         int middle = (lowerBound + upperBound) / 2;
  54:  
  55:         // base condition
  56:         if (comparer.Compare(list[middle], key) == 0)
  57:         {
  58:             return middle;       // we have found the index to the key, return it
  59:         }
  60:         // divide & conquer, the range
  61:         else if (comparer.Compare(list[middle], key) < 0) // key is in the upper half
  62:         {
  63:             return BinarySearchHelper<T>(list, comparer, key, middle + 1, upperBound);
  64:         }
  65:         else // if (comparer.Compare(list[middle], key) > 0) // key is in the lower half
  66:         {
  67:             return BinarySearchHelper<T>(list, comparer, key, lowerBound, middle - 1);
  68:         }
  69:     }
  70:  
  71:     #endregion
  72:  
  73:     #region Recursive & Functional/Lambda approach - 1
  74:  
  75:     public delegate int SearchDelegate<in TArgs>(TArgs arg, int lowerBound, int upperBound);
  76:  
  77:     public static int BinSearch2<T>(this List<T> list, T key, bool sortRequired = false)
  78:     {
  79:         Comparer<T> comparer = Comparer<T>.Default;
  80:  
  81:         return BinSearch2(list, key, comparer, sortRequired);
  82:     }
  83:  
  84:     // Recursive delegates approach, list has to be ordered/sorted
  85:     public static int BinSearch2<T>(this List<T> list, T key, IComparer<T> comparer, bool sortRequired = false)
  86:     {
  87:         if (sortRequired)
  88:         {
  89:             list.Sort(comparer);
  90:         }
  91:  
  92:         SearchDelegate<T> searchFunc = null;
  93:        
  94:         searchFunc = (xkey, lowerBound, upperBound) =>
  95:         {
  96:             // check bounds
  97:             if (lowerBound > upperBound || lowerBound < 0)
  98:             {
  99:                 return -1;  // return not found
 100:             }
 101:  
 102:             // the middle index
 103:             int middle = (lowerBound + upperBound) / 2;
 104:  
 105:             // base condition, stack un-wind
 106:             if (comparer.Compare(list[middle], xkey) == 0)
 107:             {
 108:                 return middle;       // we have found the index to the key, return it
 109:             }
 110:             else if (comparer.Compare(list[middle], xkey) < 0) // key is in the upper half
 111:             {
 112:                 return searchFunc(xkey, middle + 1, upperBound);
 113:             }
 114:             else // if (comparer.Compare(list[middle], xkey) > 0) // key is in the lower half
 115:             {
 116:                 return searchFunc(xkey, lowerBound, middle - 1);
 117:             }
 118:  
 119:         };
 120:  
 121:         // Invoked with the initial low and high values of 0 and N-1.
 122:         return searchFunc(key, 0, list.Count - 1);
 123:     }
 124:  
 125:     #endregion
 126:  
 127:     #region Recursive & Functional/lambda approach - 2
 128:  
 129:     public delegate int RecursiveDelegate<TArgs>(RecursiveDelegate<TArgs> func, TArgs arg, int lowerBound, int upperBound);
 130:  
 131:     public static int BinSearch<T>(this List<T> list, T key, bool sortRequired = false)
 132:     {
 133:         Comparer<T> comparer = Comparer<T>.Default;
 134:  
 135:         return BinSearch(list, key, comparer);
 136:     }
 137:  
 138:     /// <summary>
 139:     /// Functional  & Recursive delegates approach, list has to be ordered/sorted
 140:     /// </summary>
 141:     /// <typeparam name="T"></typeparam>
 142:     /// <param name="list"></param>
 143:     /// <param name="key"></param>
 144:     /// <param name="comparer"></param>
 145:     /// <returns></returns>
 146:     public static int BinSearch<T>(this List<T> list, T key, IComparer<T> comparer, bool sortRequired = false)
 147:     {
 148:         if (sortRequired)
 149:         {
 150:             list.Sort(comparer);
 151:         }
 152:  
 153:         RecursiveDelegate<T> searchFunc = (func, xkey, lowerBound, upperBound) =>
 154:         {
 155:             // check bounds
 156:             if (lowerBound > upperBound || lowerBound < 0)
 157:             {
 158:                 return -1;  // return not found
 159:             }
 160:  
 161:             // the middle index
 162:             int middle = (lowerBound + upperBound) / 2;
 163:  
 164:             Debug.WriteLine(middle + ", " + list[middle]);
 165:  
 166:             // base condition, stack un-wind
 167:             if (comparer.Compare(list[middle], xkey) == 0)
 168:             {
 169:                 return middle;       // we have found the index to the key, return it
 170:             }
 171:             else if (comparer.Compare(list[middle], xkey) < 0)   // key is in the upper half
 172:             {
 173:                 return func(func, xkey, middle + 1, upperBound);
 174:             }
 175:             else // if (comparer.Compare(list[middle], xkey) > 0) // key is in the lower half
 176:             {
 177:                 return func(func, xkey, lowerBound, middle - 1);
 178:             }
 179:         };
 180:  
 181:         // Invoked/called with the initial low and high values of 0 and N-1.
 182:         return searchFunc(searchFunc, key, 0, list.Count - 1);
 183:     }
 184:  
 185:  
 186:     public static int BinSearchX<T>(this List<T> list, T key, bool sortRequired = false)
 187:     {
 188:         Comparer<T> comparer = Comparer<T>.Default;
 189:  
 190:         return BinSearchX(list, key, comparer);
 191:     }
 192:  
 193:     /// <summary>
 194:     /// Functional & Recursive delegates approach, list has to be ordered/sorted
 195:     /// </summary>
 196:     /// <typeparam name="T"></typeparam>
 197:     /// <param name="list"></param>
 198:     /// <param name="key"></param>
 199:     /// <param name="comparer"></param>
 200:     /// <param name="sortRequired"></param>
 201:     /// <returns></returns>
 202:     public static int BinSearchX<T>(this List<T> list, T key, IComparer<T> comparer, bool sortRequired = false)
 203:     {
 204:         if (sortRequired)
 205:         {
 206:             list.Sort(comparer);
 207:         }
 208:  
 209:         RecursiveDelegate<T> searchFunc = (func, xkey, lowerBound, upperBound) =>
 210:         {
 211:             // check bounds
 212:             if (lowerBound > upperBound || lowerBound < 0)
 213:             {
 214:                 return -1;  // return not found
 215:             }
 216:  
 217:             // the middle index
 218:             int middle = (lowerBound + upperBound) / 2;
 219:  
 220:             if (comparer.Compare(list[middle], xkey) < 0)       // key is in the upper half
 221:             {
 222:                 return func(func, xkey, middle + 1, upperBound);
 223:             }
 224:             else if (comparer.Compare(list[middle], xkey) > 0)   // key is in the lower half
 225:             {
 226:                 return func(func, xkey, lowerBound, middle - 1);
 227:             }
 228:             else
 229:             {
 230:                 return middle;       //  base condition - we have found the index to the key, return it
 231:             }
 232:         };
 233:  
 234:         // Invoked/called with the initial low and high values of 0 and N-1.
 235:         return searchFunc(searchFunc, key, 0, list.Count - 1);
 236:     }
 237:  
 238:     #endregion
 239: }

Figure-6

Both BinSearchX, (lines#202 to 236) and BinSearch (lines#146-183)  are almost the same. There is one particular difference among these, BinSearchX uses Post-Order traversal  while BinSearch uses Pre-Order Traversal. These terminology will be very much clear when I discuss them in the context of Trees.

Now lets switch our gears with the implementation of Binary search iteratively. Take a look at the following code, Figure-7:

   1: /// <summary>
   2:  /// Binary search finds iteratively an item/key in sorted ArrayList.
   3:  /// returns zero-based index of the key/item
   4:  /// and if the item is not found returns -1
   5:  /// throws exception if the lower-bound/upper-bounds have bad indices. 
   6:  /// Note: The list needs to be ordered/sorted, if not - 
   7:  ///     pass sortRequired with true
   8:  /// </summary>
   9:  public static int BinSearchIterX<T>(this List<T> list, T key, bool sortRequired = false)
  10:  {
  11:      Comparer<T> comparer = Comparer<T>.Default;
  12:  
  13:      return BinSearchIterX(list, key, comparer, sortRequired);
  14:  }
  15:  
  16:  public static int BinSearchIterX<T>(this List<T> list, T key, IComparer<T> comparer, bool sortRequired = false)
  17:  {
  18:      return BinSearchIterX(list, key, comparer, 0, (list.Count - 1), sortRequired);
  19:  }
  20:  
  21:  /// <summary>
  22:  /// Iterative Binary search approach
  23:  /// </summary>
  24:  /// 
  25:  public static int BinSearchIterX<T>(List<T> list,
  26:      T key,
  27:      IComparer<T> comparer,            
  28:      int lowerBound,
  29:      int upperBound, 
  30:      bool sortRequired = false)
  31:  {
  32:      // Check the bounds, should not be -ve.
  33:      if (lowerBound < 0 || upperBound < 0)
  34:      {
  35:          Debug.WriteLine("Exception, lowerBound/Index of an ArrayList must not be -ve.");
  36:          
  37:          throw new IndexOutOfRangeException("Exception, lowerBound/Index of an ArrayList must not be -ve.");
  38:      }
  39:  
  40:      if (sortRequired)
  41:      {
  42:          list.Sort(comparer);
  43:      }
  44:  
  45:      int left = lowerBound;
  46:      int right = upperBound;
  47:  
  48:      while (left <= right)
  49:      {
  50:          int middle = (left + right) / 2;
  51:  
  52:          Debug.WriteLine(middle + ", " + list[middle]);
  53:  
  54:          // if the index to the key is found, return it
  55:          if (comparer.Compare(list[middle], key) == 0) 
  56:          {
  57:              return middle;
  58:          }
  59:          else if (comparer.Compare(list[middle], key) < 0)
  60:          // key is in the upper right half
  61:          {
  62:              left = middle + 1;
  63:          }
  64:          else // if (comparer.Compare(list[middle], xkey) > 0)   
  65:          // key is in the lower left half
  66:          {
  67:              right = middle - 1;
  68:          }
  69:      }
  70:  
  71:      // item not found
  72:      return -1;
  73:  }

Figure-7

If you take a look at it, the algorithm remains the same i.e. division into halves etc. but the recursion is replaced with a while loop. It is more efficient in terms  time and space, because the overhead of call-stack that is used underneath of Recursion based algorithm is eliminated. We will discuss about Recursion in detail in some later post. For the time just keep in mind that Recursion has an overhead, in respect to memory/efficiency but the complex problems are handled very easily this way. We’ll definitely talk on it later some time.

Now take a look at its usage, nothing so special same way we did before, tests for Recursive ones.

   1: // Call the following test like:
   2: // Inject the sorting dependency here
   3: // Test7(comparer);
   4:  
   5: /// <summary>
   6: /// Test Search using extension method BinSearchIter defined in BinarySearchExt
   7: /// </summary>
   8: public static void Test7(IComparer<int> comparer)
   9: {
  10:     List<int> listInts = new List<int>() { 5, 1, 7, 11, 21, 9, 77, 3, 33, 13, 15, 17, 19, 55, 66, 44, 88, 0 };
  11:  
  12:     // The List<T> must already be sorted according to the comparer implementation; otherwise, the result is incorrect.
  13:     listInts.Sort();
  14:  
  15:     // Sorted list is:
  16:     // 0 1 3 5 7 9 11 13 15 17 19 21 33 44 55 66 77 88
  17:  
  18:     // Search using extension method BinSearchIterX defined in BinarySearchExt
  19:     // int index = listInts.BinSearchIterX(88);
  20:     int index = listInts.BinSearchIterX(11, comparer);
  21:  
  22:     Debug.Assert(index == 6);
  23:  
  24:     Debug.WriteLine("Test7.BinSearchIterX | Passed | result index: " + index);
  25: }
  26:     }

Figure-8

As discussed earlier, Analysis of the Binary-Search Algorithm on the average yields  O(logN) searches/probes.

That's all for now folks, I hope it was helpful. I appreciate you please leave your valuable feedback. Enjoy :)

If you enjoyed reading this blog, leave your valuable feedback and consider subscribing to the RSS feed. You can also subscribe to it by email. Also, you can follow me on Twitter. Thank you!

Comments (1) -

игровые слоты slot78
10/11/2017 4:27:19 PM #

I would like to thank you for the efforts you've put in writing this blog. I'm hoping to view the same high-grade blog posts from you later on as well. In fact, your creative writing abilities has motivated me to get my own, personal site now ;)

Do you mind if I quote a few of your posts as long as I provide credit and sources back to your site? My website is in the very same area of interest as yours and my users would genuinely benefit from some of the information you present here. Please let me know if this ok with you. Thank you!  my web blog:  Аренда квартир в Аликанте - www.0dyx.cn/home.php

fantastic issues altogether, you just received a new reader. What might you recommend in regards to your post that you just made some days in the past? Any positive?

Wonderful article! We are linking to this particularly great content on our site. Keep up the great writing.

I used to be recommended this web site via my cousin. I am now not certain whether this put up is written through him as no one else understand such certain approximately my trouble. You're incredible! Thank you!

I do consider all the ideas you have introduced for your post. They are really convincing and will definitely work. Still, the posts are very quick for newbies. Could you please prolong them a bit from subsequent time? Thank you for the post.  My web-site ...  storage.googleapis.com/.../...lancha-CA-93549.html - storage.googleapis.com/.../...lancha-CA-93549.html

xarelto lawyers
10/16/2017 6:59:51 PM #

I hardly write comments, however i did some searching and wound up here GeeksCafe.NET | Back to basics – Part o..of..n-1 – Binary Search Algorithm Explained using C#. And I do have a couple of questions for you if you do not mind. Could it be just me or does it seem like a few of the responses appear like written by brain dead people? :-P And, if you are writing on other social sites, I'd like to keep up with anything fresh you have to post. Could you make a list of every one of your community sites like your Facebook page, twitter feed, or linkedin profile?  Feel free to surf to my web page:  xarelto lawyers - xareltolaw.bitbucket.org/.../index.html

Gertie
10/16/2017 9:57:54 PM #

Today, I went to the beach front with my children. I found a sea shell and gave it to my 4 year old daughter and said "You can hear the ocean if you put this to your ear." She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!  My weblog  Gertie - enfoe.it/corsi-di-inglese-a-torino-principianti/

http://compilationfacialamateur.tk/
10/17/2017 8:52:42 AM #

wwwplancul.tk
10/18/2017 9:52:26 PM #

Je vind hier dus niet alleen maar rijpe Vrouwen die zin hebben in ouderensex tot bejaardensex.

If you are going for best contents like me, just visit this web page everyday since it offers feature contents, thanks

Hello! I'm at work browsing your blog from my new iphone 4! Just wanted to say I love reading your blog and look forward to all your posts! Keep up the superb work!

We absolutely love your blog and find nearly all of your post's to be just what I'm looking for. can you offer guest writers to write content for yourself? I wouldn't mind creating a post or elaborating on a lot of the subjects you write with regards to here. Again, awesome web log!

Hello! I understand this is kind of off-topic but I needed to ask. Does running a well-established blog like yours take a lot of work? I'm completely new to blogging but I do write in my diary on a daily basis. I'd like to start a blog so I can share my personal experience and thoughts online. Please let me know if you have any kind of recommendations or tips for brand new aspiring bloggers. Thankyou!

Add comment