C#折半查找

    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;
                }
                else//如果要查找元素大于中间位置元素，把中间位置后面的索引设为低点
                {
                    low = middle + 1;
                }
                //如果代码运行到此处，说明还没有找到匹配元素，由于以上重新设置了低点或高点，所以这里也要重新设置中间位置
                middle = (low + high + 1)/2;
            } while ((low <= high) && (location == -1));
            return location;
        }
        //打印2个位置间的数组元素
        public string PrintSectionElements(int low, int high)
        {
            string temp = "";
            //对于2个位置间的元素打印出元素并跟上一个空格位置
            for (int i = low; i <= high; i++)
            {
                temp += arr[i] + " ";
            }
            return temp;
        }
        //重写ToString方法，把数组所有的元素都打印出来
        public override string ToString()
        {
            return PrintSectionElements(0, arr.Length - 1);
        }
    }

    class Program
    {
        private static int key; //需查找元素
        private static int position;//匹配元素所在的位置
        static void Main(string[] args)
        {
            MyArray myArray = new MyArray(7);
            //把所有元素打印出来
            Console.WriteLine(myArray);
            Console.WriteLine("请输入需要查找的元素或输入-1退出 ");
            key = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine();
            while (key != -1)
            {
                //调用折半算法得出所需查找元素的位置
                position = myArray.HalfSearch(key);
                if (position == -1) //说明没有找到需要匹配的元素
                {
                    Console.WriteLine("没有找到元素{0}", key);
                }
                else
                {
                    Console.WriteLine("在{0}号位置查到元素{1}", position, key);
                }
                Console.WriteLine("请输入需要查找的元素或输入-1退出 ");
                key = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine();
            }
        }
    }