插值查找

  public class InsertValueSearch
    {
        /// <summary>
        /// 插值查找算法(需要数组是有序的)
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="left">左边索引</param>
        /// <param name="right">右边索引</param>
        /// <param name="findval">查找值</param>
        /// <returns>值的下标</returns>
        public static int Search(int[] arr, int left,int right,int findval)
        {
            //必须需要，否则得到的mid的值可能越界。
            if (left > right || findval < arr[0] || findval > arr[arr.Length - 1])
            {
                return -1;
            }
            //求出mid
            int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left]);
            int midVal = arr[mid];
            if (findval > midVal)
            {
                //说明应该向右边进行查找
                return Search(arr, mid + 1, right, findval);
            }
            else if (findval < midVal)
            {
                return Search(arr, left, mid - 1, findval);
            }
            else
            {
                return mid;
            }
        }
    }

        static void Main(string[] args)
        {
            //数组进行升序排序
            int[] arr = { 1, 8, 10, 89, 1000, 1234 };
            var result = InsertValueSearch.Search(arr, 0,arr.Length -1 , 1000);
            Console.WriteLine(result);
            Console.Read();
        }

    static void Main(string[] args)
        {
            //初始化一个有序的100长度的数组
            int[] arr = new int[100];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = i + 1;
            }
            //使用二分查找，并在方法内部加一个打印，输出几次代表执行了几次
            var result = BinarySearch.Search(arr,0,arr.Length,100);
            //使用插值查找，并在方法内部加一个打印，输出几次代表执行了几次
            var result0 = InsertValueSearch.Search(arr, 0,arr.Length -1 , 1000);
            Console.Read();
        }