二分查找法（折半查找）

笨鸟开始飞的博客 / 2023-08-21 / 原文

二分查找法是一种在有序数组中查找特定元素的算法。为了理解它的工作原理，我们需要知道数组是有序的，也就是说，数组中的元素按照升序或降序排列。

二分查找法的基本步骤如下：

选择数组的中间元素。
如果中间元素正好是目标值，则搜索结束。
如果目标值大于中间元素，则只需在数组的右半部分中查找。
如果目标值小于中间元素，则只需在数组的左半部分中查找。
重复以上步骤，直到找到目标值或者确定目标值不在数组中。

因为每次搜索都会将搜索范围减半，所以算法非常快速和高效。

        /// <summary>
        /// 二分查找法（折半查找）
        /// </summary>
        public static void MethodMain()
        {
            int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
            int length = array.Length;
            int searchVal = 15;
            int resultByRecursion = BinarySearchByRecursion(array, 0, length - 1, searchVal);
            int resultByWhile = BinarySearchByWhile(array, searchVal);

            if (resultByRecursion != resultByWhile)
            {
                Console.WriteLine("两个算法结果不一致，结果错误");
            }
            else
            {
                Console.WriteLine("Element found at index " + resultByRecursion);
            }
        }

        /// <summary>
        /// 二分查找法(递归实现)
        /// </summary>
        /// <param name="array">数组</param>
        /// <param name="firstIndex">查找范围的开始</param>
        /// <param name="length">查找范围的长度</param>
        /// <param name="target">查找目标</param>
        /// <returns></returns>
        public static int BinarySearchByRecursion(int[] array, int firstIndex, int length, int target)
        {
            //判断是否超过检索范围
            if (firstIndex > length)
                return -1;

            //获取中间索引
            int midIndex = firstIndex + (length - firstIndex) / 2;

            //中间索引的值
            int midVal = array[midIndex];

            if (midVal > target)        //中间索引值大于目标值则在左半边继续进行二分法查询
                return BinarySearchByRecursion(array, firstIndex, midIndex - 1, target);
            else if (midVal < target)   //目标值大于中间索引值则在右半边继续进行二分法查询
                return BinarySearchByRecursion(array, midIndex + 1, length, target);
            else                        //进行对比，值一致则返回
                return midIndex;
        }


        /// <summary>
        /// 二分查找法(循环实现)
        /// </summary>
        /// <param name="arr">数组</param>
        /// <param name="target">查询目标值</param>
        /// <returns></returns>
        public static int BinarySearchByWhile(int[] arr, int target)
        {
            int length = arr.Length - 1;
            int firstIndex = 0;

            //判断是否超过检索范围
            while (firstIndex <= length)
            {
                //获取中间索引
                int mindIndex = firstIndex + (length - firstIndex) / 2;
                //中间索引的值
                int mindVal = arr[mindIndex];


                if (mindVal > target)
                {//中间索引值大于目标值则在左半边继续进行二分法查询
                    length = mindIndex - 1;
                }
                else if (mindVal < target)
                {//目标值大于中间索引值则在右半边继续进行二分法查询
                    firstIndex = mindIndex + 1;
                }
                else
                {//进行对比，值一致则返回
                    return mindIndex;
                }
            }
            return -1;
        }