查找與排序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;