Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- class Program
- {
- /// <summary>
- /// Find missing number in ordered list of integers
- /// </summary>
- /// <param name="list">Integer list</param>
- /// <returns>Missing number</returns>
- public static int FindMissingNumber(IList<int> list)
- {
- if (list == null) throw new ArgumentNullException("list");
- return FindMissingNumber(list, 0, list.Count);
- }
- /// <summary>
- /// Recursively find missing missing number in ordered list
- /// </summary>
- /// <param name="a">Lower bound</param>
- /// <param name="b">Upper bound</param>
- /// <returns>Missing number</returns>
- private static int FindMissingNumber(IList<int> list, int a, int b)
- {
- // Find midpoint (m)
- var m = a + (b - a) / 2;
- if (a == b) return m + 1;
- if (list[m] == m) return m;
- if (list[m] == m + 1) return FindMissingNumber(list, m + 1, b);
- return FindMissingNumber(list, a, m);
- }
- static void Main(string[] args)
- {
- Action<IList<int>> Time = list =>
- {
- var timer = System.Diagnostics.Stopwatch.StartNew();
- var result = FindMissingNumber(list);
- timer.Stop();
- Console.WriteLine(
- "Result {0} Elapsed: {1}ms",
- result,
- timer.ElapsedMilliseconds);
- };
- Time(new[] {2,3,4});
- Time(new[] {1,2,3});
- Time(new[] {1,3,4});
- var tenMillion = new int[10000000];
- for(int i = 0; i < tenMillion.Length; i++) tenMillion[i]= i+1;
- Time(tenMillion);
- return;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement