查找算法之二分查找

二分查找的两种实现方式

namespace DataStructureAndAlgorithm.Search
{
    /// <summary>
    /// 二分查找算法
    /// </summary>
    public class BinarySearch
    {
        public static void Test()
        {
            int[] arrs = { 1,3,7,23,44,55 };
            int index = SearchWhile(arrs, 23);
            index = SearchDiGui(arrs, 0, arrs.Length - 1, 23);
            index = SearchWhile(arrs, 100);
            index = SearchDiGui(arrs, 0, arrs.Length - 1, 100);
            index = SearchWhile(arrs, 44);
            index = SearchDiGui(arrs, 0, arrs.Length - 1, 44);
        }
        /// <summary>
        /// 方法一：用While实现
        /// </summary>
        /// <param name="arrs"></param>
        /// <param name="val"></param>
        /// <returns></returns>
        public  static int SearchWhile(int [] arrs,int val)
        {
            int leftIndex = 0;
            int rightIndex = arrs.Length - 1;
            while (leftIndex <= rightIndex)
            {
                int midIndex = (leftIndex + rightIndex) / 2;
                int midVal = arrs[midIndex];
                if (val > midVal)
                {
                    //向右查找
                    leftIndex = midIndex + 1;
                }
                else if (val < midVal)
                {
                    //向左查找
                    rightIndex = midIndex - 1;
                }
                else if (val == midVal)
                {
                    //找到了
                    return midIndex;
                }
            }
            //没找到
            return -1;
        }

        /// <summary>
        /// 方法二：用递归实现
        /// </summary>
        /// <param name="arrs"></param>
        /// <param name="leftIndex"></param>
        /// <param name="rightIndex"></param>
        /// <param name="val"></param>
        /// <returns></returns>
        public static int SearchDiGui(int[] arrs,int leftIndex,int rightIndex,int val)
        {
            if (leftIndex > rightIndex)
            {
                //没找到
                return -1;
            }
            int midIndex = (leftIndex + rightIndex) / 2;
            if (val == arrs[midIndex])
            {
                //找到了
                return midIndex;
            }
            else if (val > arrs[midIndex])
            {
                //向右查找
                return SearchDiGui(arrs, midIndex + 1, rightIndex, val);
            }
            else
            {
                //向左查找
                return SearchDiGui(arrs, leftIndex, midIndex - 1, val);
            }
        }
    }
}