using System;
using System.Collections.Generic;
using System.Text;

namespace AAA
{
    public class Dichotomy
    {
        public static void DichotomySort(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                int start = 0;

                int end = i - 1;

                int middle = 0;

                int temp = array[i];

                while (start <= end)
                {
                    middle = (start + end) / 2;

                    if (array[middle] > temp)//要排序元素在已经排过序的数组左边
                    {
                        end = middle - 1;
                    }
                    else
                    {
                        start = middle + 1;
                    }
                }
                for (int j = i - 1; j > end; j--)//找到了要插入的位置，然后将这个位置以后的所有元素向后移动
                {
                    array[j + 1] = array[j];
                }

                array[end + 1] = temp;

            }
        }

        public static long DichotomySearch(long[] array, long key, long high, long low)
        {
            long middle = 0;

            if (high < low)
            {
                return -1;
            }

            middle = (low + high) / 2;

            if (array[middle] == key)
            {
                return middle;
            }
            else if (array[middle] > key)
            {
                return DichotomySearch(array, key, middle - 1, low);
            }
            else
            {
                return DichotomySearch(array, key,high, middle + 1);
            }
        }
    }
}