My Pastes
Public Pastes
Layout Width
Share Pastebin
Guest
Public paste!

mgroves

By: a guest | Apr 25th, 2009 | Syntax: C# | Size: 5.55 KB | Hits: 280 | Expires: Never
Download | Raw | Embed | Report abuse
Copy text to clipboard
  1. using System;
  2. using MbUnit.Framework;
  3.  
  4. namespace codekata2___karate_chop
  5. {
  6.     [TestFixture]
  7.     public class TestChop
  8.     {
  9.         [Test]
  10.         public void test_chop()
  11.         {
  12.             Assert.AreEqual(-1, chop(3, new int[] { }));
  13.             Assert.AreEqual(-1, chop(3, new[] { 1 }));
  14.             Assert.AreEqual(0, chop(1, new[] { 1 }));
  15.  
  16.             Assert.AreEqual(0, chop(1, new[] { 1, 3, 5 }));
  17.             Assert.AreEqual(1, chop(3, new[] { 1, 3, 5 }));
  18.             Assert.AreEqual(2, chop(5, new[] { 1, 3, 5 }));
  19.             Assert.AreEqual(-1, chop(0, new[] { 1, 3, 5 }));
  20.             Assert.AreEqual(-1, chop(2, new[] { 1, 3, 5 }));
  21.             Assert.AreEqual(-1, chop(4, new[] { 1, 3, 5 }));
  22.             Assert.AreEqual(-1, chop(6, new[] { 1, 3, 5 }));
  23.  
  24.             Assert.AreEqual(0, chop(1, new[] { 1, 3, 5, 7 }));
  25.             Assert.AreEqual(1, chop(3, new[] { 1, 3, 5, 7 }));
  26.             Assert.AreEqual(2, chop(5, new[] { 1, 3, 5, 7 }));
  27.             Assert.AreEqual(3, chop(7, new[] { 1, 3, 5, 7 }));
  28.             Assert.AreEqual(-1, chop(0, new[] { 1, 3, 5, 7 }));
  29.             Assert.AreEqual(-1, chop(2, new[] { 1, 3, 5, 7 }));
  30.             Assert.AreEqual(-1, chop(4, new[] { 1, 3, 5, 7 }));
  31.             Assert.AreEqual(-1, chop(6, new[] { 1, 3, 5, 7 }));
  32.             Assert.AreEqual(-1, chop(8, new[] { 1, 3, 5, 7 }));
  33.         }
  34.  
  35.         // recursive
  36.         private int chop_recursive(int search, int[] intlist)
  37.         {
  38.             if(intlist.Length == 0)
  39.             {
  40.                 return -1;
  41.             }
  42.  
  43.             int middleindex = (intlist.Length) / 2;
  44.  
  45.             if(intlist[middleindex] == search)
  46.             {
  47.                 return (middleindex);
  48.             }
  49.  
  50.             if(intlist.Length == 1)
  51.             {
  52.                 return (-1);
  53.             }
  54.  
  55.             if (search > intlist[middleindex])
  56.             {
  57.                 // chop search on 2nd half
  58.                 int secondhalflength = intlist.Length - middleindex - 1;
  59.                 int[] secondhalflist = new int[secondhalflength];
  60.                 Array.Copy(intlist, middleindex+1, secondhalflist, 0, secondhalflength);
  61.                 int result = chop(search, secondhalflist);
  62.                 if(result != -1)
  63.                 {
  64.                     return (1 + middleindex + chop(search, secondhalflist));
  65.                 }
  66.                 return (result);
  67.             }
  68.             // chop search on 1st half
  69.             int[] firsthalflist = new int[middleindex];
  70.             Array.Copy(intlist, 0, firsthalflist, 0, middleindex);
  71.             return (chop(search, firsthalflist));
  72.         }
  73.  
  74.         // iterative
  75.         private int chop_iterative(int search, int[] intlist)
  76.         {
  77.             if(intlist.Length == 0)
  78.             {
  79.                 return (-1);
  80.             }
  81.  
  82.             int middleindex = (intlist.Length) / 2;
  83.             int mindex = 0;
  84.             int maxdex = intlist.Length - 1;
  85.             while (true)
  86.             {
  87.                 if (search == intlist[middleindex])
  88.                 {
  89.                     return (middleindex);
  90.                 }
  91.                 if((maxdex-mindex)<=1 && (search!=intlist[middleindex]))
  92.                 {
  93.                     return (-1);
  94.                 }
  95.                 if (search > intlist[middleindex])
  96.                 {
  97.                     mindex = middleindex + 1;
  98.                     maxdex = intlist.Length - 1;
  99.                 }
  100.                 else
  101.                 {
  102.                     mindex = 0;
  103.                     maxdex = middleindex;
  104.                 }
  105.                 middleindex = mindex + ((maxdex - mindex)/2);
  106.             }
  107.         }
  108.  
  109.         // single comparison per iteration
  110.         // from: http://en.wikipedia.org/wiki/Binary_search#Implementations
  111.         private int chop_single_compare(int search, int[] intlist)
  112.         {
  113.             int low = 0;
  114.             int high = intlist.Length;
  115.             while(low < high)
  116.             {
  117.                 int mid = low + ((high - low)/2);
  118.                 if (intlist[mid] < search)
  119.                 {
  120.                     low = mid + 1;
  121.                 }
  122.                 else
  123.                 {
  124.                     high = mid;
  125.                 }
  126.             }
  127.             if ((low < intlist.Length) && (intlist[low] == search))
  128.             {
  129.                 return (low);
  130.             }
  131.             return (-1);
  132.         }
  133.  
  134.         // cheating implementation using framework built in Array binarysearch
  135.         private int chop_cheat(int search, int[] intlist)
  136.         {
  137.             int result = Array.BinarySearch(intlist, search);
  138.             if(result < 0)
  139.             {
  140.                 result = -1;
  141.             }
  142.             return (result);
  143.         }
  144.  
  145.         // variation on single compare with max two compares per iteration
  146.         // from: http://en.wikibooks.org/wiki/Algorithm_implementation/Search/Binary_search#C.23_.28common_Algorithm.29
  147.         private int chop(int search, int[] intlist)
  148.         {
  149.             int low = 0;
  150.             int high = intlist.Length - 1;
  151.             while(low <= high)
  152.             {
  153.                 int midpoint = (low + high)/2;
  154.  
  155.                 if(search == intlist[midpoint])
  156.                 {
  157.                     return (midpoint);
  158.                 }
  159.                 if (search < intlist[midpoint])
  160.                 {
  161.                     high = midpoint - 1;
  162.                 }
  163.                 else
  164.                 {
  165.                     low = midpoint + 1;
  166.                 }
  167.             }
  168.             return -1;
  169.         }
  170.     }
  171. }
create new paste | create new version of this paste RAW Paste Data