查找与排序02,折半查找

折半查找，也叫二分查找，当在一个数组或集合中查找某个元素时，先定位出中间位置元素，如果要查找的元素正好和该中间位置元素相等，通过一次查找，就能找到匹配元素；如果要查找的元素小于该中间位置元素，就抛弃后面一半的元素，在前面一半的元素中再定位出中间位置元素，如此反复，直到找到匹配元素；如果要查找的元素大于该中间位置元素，就抛弃前面一半的元素，在后面一半的元素中定位出中间位置元素，如此反复。

面临的第一个问题是：中间位置元素如何定位？在折半查找中规定：当元素个数是奇数，比如有3个元素，中间位置元素是索引为1的元素；当元素个数是偶数，比如有4个元素，索引为1和2的元素理论都是中间位置元素，但在折半查找中，把后面这个，即索引为2的元素视为中间位置元素。

面临的第二个问题是：由于，要查找的元素和中间位置元素之间需要比较，我们在比较之前，势必要让数组按升序或降序来排列。

自定义一个类，该类维护着一个int[]类型数组，通过构造函数确定数组长度和对数组进行排序，并提供打印数组元素的方法，以及折半算法。

    public class MyArray
    {
        PRivate int[] arr;//内部维护着一个数组
        private static Random r = new Random();//用它来生成数组的随机元素
        //通过构造函数来确定内部数组的长度，并生成数组的随机元素,并对数组元素排序
        public MyArray(int size)
        {
            arr = new int[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = r.Next(1, 100);
            }
            Array.Sort(arr);
        }
        //折半查找算法 返回查找元素的索引位置
        public int HalfSearch(int key)
        {
            int low = 0;//低点，初始值设置成最低点，即索引0
            int high = arr.Length - 1;//高点，初始值设置成最高点，即索引数组最后一个位置
            //如果数组元素个数是偶数，比如4个，索引2和3都是中间位置，用以下算法中间位置指向索引3
            //如果数组元素个数是奇数，比如3个，索引1是中间位置，用以下算法中间位置指向索引1
            int middle = (low + high + 1)/2;
            int location = -1;//找不到就返回-1
            //循环，找不到就一直查找
            do
            {
                //每次循环，把低点和高点位置的元素打印出来
                Console.WriteLine(PrintSectionElements(low, high));
                Console.WriteLine();
                //如果要查找元素是中间位置的元素，就返回中间位置这个索引
                if (key == arr[middle])
                {
                    location = middle;
                }
                else if (key < arr[middle]) //如果要查找元素小于中间位置元素，把中间位置前面的索引设为高点
                {
                    high = middle - 1;