C# 实现二分查找

前言

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

这种搜索算法每一次比较都使搜索范围缩小一半。

C#代码

 static void Main(string[] args)
        {
            /*
                  ====折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。=====
                  A 搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
                  B 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
                  C 如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
                  时间复杂度折半搜索每次把搜索区域减少一半
                  "科学计算器中的对数log"是以10为底的对数
                  如果你要算log2(20).....以2为底的对数
                  那你先换底,log2(20)=lg20/lg2
                  计算器中的具体按法:"20","log","/","2","log","="  结果4.3219280948873623478703194294894
                  计算器中的具体按法:"32","log","/","2","log","="  结果5
               */
            int[] y = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
            int loopCount = 0;
            // int rr = BinarySearch(y, 0, y.Length - 1, 13, ref loopCount); //查找数并返回 若有，返回该数，没有则返回-1
            int rr = BinarySearch2(y,8, ref loopCount);
            Console.Write("查找次数{0} 索引{1}", loopCount, rr); 

            Console.ReadKey();
        }
        /// <summary>
        /// 二分查找返回索引,不存在则返回-1
        /// </summary>
        /// <param name="arr">数组</param>
        /// <param name="startIndex">开始索引 0</param>
        /// <param name="endIndex">结束索引 </param>
        /// <param name="key">要查找的对象</param>
        /// <param name="count">查找次数</param>
        /// <returns></returns>
        public static int BinarySearch(int[] arr, int startIndex, int endIndex, int key, ref int count)
        {
            //查找次数
            count++;

            //定义下标(折半)
            var index = (startIndex + endIndex) / 2;

            //所有值都找完了,没有符合条件的值
            if (startIndex > endIndex)
                return -1;

            //如果等于目标值
            if (arr[index] == key) 
                return index; 
            //如果大于目标值，则证明在另外一个区间内
            else if (arr[index] > key) 
              return  BinarySearch(arr, startIndex, index - 1, key, ref count); 
            //如果小于目标值，则证明在另外一个区间内
            else 
               return BinarySearch(arr, index + 1, endIndex, key, ref count); 

        }

        /// <summary>
        /// 二分查找非递归方法
        /// </summary>
        /// <param name="arr">数组</param>
        /// <param name="key">要查找的对象</param>
        /// <param name="count">查找次数</param>
        /// <returns></returns>
        public static int BinarySearch2(int[] arr,int key,ref int count) 
        {
            //定义开始索引
            int startIndex = 0;
            //定义结束索引
            int endIndex = arr.Length - 1;
            //定义下标(折半)
            var index = 0;

            while (startIndex<= endIndex)
            {
                count++;
                index = (startIndex + endIndex) / 2;
                if (arr[index]> key)
                {
                    endIndex = index - 1;
                }
                else if (arr[index] < key)
                {
                    startIndex = index + 1;
                }
                else
                {
                   return index;
                } 
            }
            return -1; 
        }