Advertisement
ptrelford

Find Missing Number recursive

Nov 7th, 2013
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.68 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. class Program
  5. {    
  6.     /// <summary>
  7.     /// Find missing number in ordered list of integers
  8.     /// </summary>
  9.     /// <param name="list">Integer list</param>
  10.     /// <returns>Missing number</returns>
  11.     public static int FindMissingNumber(IList<int> list)
  12.     {
  13.         if (list == null) throw new ArgumentNullException("list");
  14.         return FindMissingNumber(list, 0, list.Count);
  15.     }
  16.  
  17.     /// <summary>
  18.     /// Recursively find missing missing number in ordered list
  19.     /// </summary>
  20.     /// <param name="a">Lower bound</param>
  21.     /// <param name="b">Upper bound</param>
  22.     /// <returns>Missing number</returns>
  23.     private static int FindMissingNumber(IList<int> list, int a, int b)
  24.     {        
  25.         // Find midpoint (m)
  26.         var m = a + (b - a) / 2;
  27.         if (a == b) return m + 1;
  28.         if (list[m] == m) return m;
  29.         if (list[m] == m + 1) return FindMissingNumber(list, m + 1, b);
  30.         return FindMissingNumber(list, a, m);
  31.     }
  32.  
  33.     static void Main(string[] args)
  34.     {
  35.         Action<IList<int>> Time = list =>
  36.         {
  37.             var timer = System.Diagnostics.Stopwatch.StartNew();
  38.             var result = FindMissingNumber(list);
  39.             timer.Stop();
  40.             Console.WriteLine(
  41.                 "Result {0} Elapsed: {1}ms",
  42.                     result,
  43.                     timer.ElapsedMilliseconds);
  44.         };
  45.  
  46.         Time(new[] {2,3,4});
  47.         Time(new[] {1,2,3});
  48.         Time(new[] {1,3,4});
  49.         var tenMillion = new int[10000000];
  50.         for(int i = 0; i < tenMillion.Length; i++) tenMillion[i]= i+1;
  51.         Time(tenMillion);
  52.         return;
  53.     }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement