Interpolation search (binary search upgraded)

algorithm.interpolation.search.cs

using System;

namespace interpolation
{
    class Program
    {
        //usage: dotnet run 1 2 3 4 7 10 13
        static void Main(string[] args)
        {
            //pseudocode https://www.tutorialspoint.com/data_structures_algorithms/interpolation_search_algorithm.htm
            //O worst: n, best case: log(log(n))
            Console.WriteLine("Hello World!" + String.Join(",", args));

            int[] arr = new int[args.Length];

            for (int i = 0; i < args.Length; i++)
            {
                arr[i] = Int32.Parse(args[i]);
            }

            if (arr.Length == 0)
                arr = new int[4]{
                    2,3,7,9
                };

            int lower = 0;
            int upper = Math.Max(0, arr.Length - 1);
            int mid = -1;
            int x = 7;
            int found = -1;

            while (lower != upper && arr[lower] != arr[upper])
            {
                mid = lower + (
                    (upper - lower) / (arr[upper] - arr[lower]) * (x - arr[lower])
                );

                if (arr[mid] == x)
                {
                    found = mid;
                    break;
                }

                if (arr[mid] < x)
                {
                    lower = mid + 1;
                } else if (arr[mid] > x){
                    upper = mid - 1;
                }
            }

            Console.WriteLine("index of " + x + " is " + found);
        }
    }
}