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

Posted by Shams Mukhtar | Comments (297) | 19. April 2011

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 : ) .

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

Add comment


(Will show your Gravatar icon)  

biuquote
  • Comment
  • Preview
Loading