学步园

• 递归实现：

// --------------------------------------------------------------------------------------------------------------------
// <copyright company="Chimomo's Company" file="Program.cs">
// Respect the work.
// </copyright>
// <summary>
// The binary search (recursive).
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace CSharpLearning
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    internal class Program
    {
        /// <summary>
        /// The binary search (recursive).
        /// 在下界为low，上界为high的有序数组a中折半查找数据元素x（递归）。
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="x">
        /// The x.
        /// </param>
        /// <param name="low">
        /// The low.
        /// </param>
        /// <param name="high">
        /// The high.
        /// </param>
        /// <returns>
        /// The <see cref="int"/>.
        /// </returns>
        public static int BinarySearch(int[] a, int x, int low, int high)
        {
            if (low > high)
            {
                return -1;
            }

            int mid = (low + high) / 2;
            if (x == a[mid])
            {
                return mid;
            }

            return x < a[mid] ? BinarySearch(a, x, low, mid - 1) : BinarySearch(a, x, mid + 1, high);
        }

        /// <summary>
        /// Entry point into console application.
        /// </summary>
        private static void Main()
        {
            int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Console.WriteLine(BinarySearch(a, 6, 0, 9));
        }
    }
}

// Output:
/*
5
*/

时间复杂度：O(log₂n)

• 非递归实现：

// --------------------------------------------------------------------------------------------------------------------
// <copyright company="Chimomo's Company" file="Program.cs">
// Respect the work.
// </copyright>
// <summary>
// The binary search (not recursive).
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace CSharpLearning
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    internal class Program
    {
        /// <summary>
        /// The binary search (not recursive).
        /// 在长度为n的有序数组a中查找值为key的元素（非递归）。
        /// </summary>
        /// <summary>
        /// 在长度为n的数组a中查找值为key的元素。
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="key">
        /// The key.
        /// </param>
        /// <param name="n">
        /// The n.
        /// </param>
        /// <returns>
        /// The <see cref="int"/>.
        /// </returns>
        public static int BinarySearch(int[] a, int key, int n)
        {
            int low = 0;
            int high = n - 1;
            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (a[mid] == key)
                {
                    return mid;
                }

                if (a[mid] < key)
                {
                    low = mid + 1;
                }
                else
                {
                    high = mid - 1;
                }
            }

            return -1;
        }

        /// <summary>
        /// Entry point into console application.
        /// </summary>
        private static void Main()
        {
            int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Console.WriteLine(BinarySearch(a, 6, 9));
        }
    }
}

// Output:
/*
5
*/

时间复杂度：O(log₂n)