C#實(shí)現(xiàn)折半查找算法

更新時(shí)間：2022年08月13日 15:39:44 作者：Darren?Ji

這篇文章介紹了C#實(shí)現(xiàn)折半查找的算法，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

折半查找，也叫二分查找，當(dāng)在一個(gè)數(shù)組或集合中查找某個(gè)元素時(shí)，先定位出中間位置元素，如果要查找的元素正好和該中間位置元素相等，通過一次查找，就能找到匹配元素；如果要查找的元素小于該中間位置元素，就拋棄后面一半的元素，在前面一半的元素中再定位出中間位置元素，如此反復(fù)，直到找到匹配元素；如果要查找的元素大于該中間位置元素，就拋棄前面一半的元素，在后面一半的元素中定位出中間位置元素，如此反復(fù)。

面臨的第一個(gè)問題是：中間位置元素如何定位？在折半查找中規(guī)定：當(dāng)元素個(gè)數(shù)是奇數(shù)，比如有3個(gè)元素，中間位置元素是索引為1的元素；當(dāng)元素個(gè)數(shù)是偶數(shù)，比如有4個(gè)元素，索引為1和2的元素理論都是中間位置元素，但在折半查找中，把后面這個(gè)，即索引為2的元素視為中間位置元素。

面臨的第二個(gè)問題是：由于，要查找的元素和中間位置元素之間需要比較，我們?cè)诒容^之前，勢(shì)必要讓數(shù)組按升序或降序來(lái)排列。

自定義一個(gè)類，該類維護(hù)著一個(gè)int[]類型數(shù)組，通過構(gòu)造函數(shù)確定數(shù)組長(zhǎng)度和對(duì)數(shù)組進(jìn)行排序，并提供打印數(shù)組元素的方法，以及折半算法。

    public class MyArray
    {
        private int[] arr;//內(nèi)部維護(hù)著一個(gè)數(shù)組
        private static Random r = new Random();//用它來(lái)生成數(shù)組的隨機(jī)元素
        //通過構(gòu)造函數(shù)來(lái)確定內(nèi)部數(shù)組的長(zhǎng)度，并生成數(shù)組的隨機(jī)元素,并對(duì)數(shù)組元素排序
        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;//低點(diǎn)，初始值設(shè)置成最低點(diǎn)，即索引0
            int high = arr.Length - 1;//高點(diǎn)，初始值設(shè)置成最高點(diǎn)，即索引數(shù)組最后一個(gè)位置
            //如果數(shù)組元素個(gè)數(shù)是偶數(shù)，比如4個(gè)，索引2和3都是中間位置，用以下算法中間位置指向索引3
            //如果數(shù)組元素個(gè)數(shù)是奇數(shù)，比如3個(gè)，索引1是中間位置，用以下算法中間位置指向索引1
            int middle = (low + high + 1)/2;
            int location = -1;//找不到就返回-1
            //循環(huán)，找不到就一直查找
            do
            {
                //每次循環(huán)，把低點(diǎn)和高點(diǎn)位置的元素打印出來(lái)
                Console.WriteLine(PrintSectionElements(low, high));
                Console.WriteLine();
                //如果要查找元素是中間位置的元素，就返回中間位置這個(gè)索引
                if (key == arr[middle])
                {
                    location = middle;
                }
                else if (key < arr[middle]) //如果要查找元素小于中間位置元素，把中間位置前面的索引設(shè)為高點(diǎn)
                {
                    high = middle - 1;
                }
                else//如果要查找元素大于中間位置元素，把中間位置后面的索引設(shè)為低點(diǎn)
                {
                    low = middle + 1;
                }
                //如果代碼運(yùn)行到此處，說明還沒有找到匹配元素，由于以上重新設(shè)置了低點(diǎn)或高點(diǎn)，所以這里也要重新設(shè)置中間位置
                middle = (low + high + 1)/2;
            } while ((low <= high) && (location == -1));
            return location;
        }
        //打印2個(gè)位置間的數(shù)組元素
        public string PrintSectionElements(int low, int high)
        {
            string temp = "";
            //對(duì)于2個(gè)位置間的元素打印出元素并跟上一個(gè)空格位置
            for (int i = low; i <= high; i++)
            {
                temp += arr[i] + " ";
            }
            return temp;
        }
        //重寫ToString方法，把數(shù)組所有的元素都打印出來(lái)
        public override string ToString()
        {
            return PrintSectionElements(0, arr.Length - 1);
        }
    }

以上，折半查找的目的是找到匹配元素在數(shù)組中的索引位置，為此，通過需查找元素和中間位置元素大小的比較，不斷地調(diào)整低點(diǎn)、高點(diǎn)和中間位置。另外，在C#中，1/2的結(jié)果是0。

客戶端。

    class Program
    {
        private static int key; //需查找元素
        private static int position;//匹配元素所在的位置
        static void Main(string[] args)
        {
            MyArray myArray = new MyArray(7);
            //把所有元素打印出來(lái)
            Console.WriteLine(myArray);
            Console.WriteLine("請(qǐng)輸入需要查找的元素或輸入-1退出 ");
            key = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine();
            while (key != -1)
            {
                //調(diào)用折半算法得出所需查找元素的位置
                position = myArray.HalfSearch(key);
                if (position == -1) //說明沒有找到需要匹配的元素
                {
                    Console.WriteLine("沒有找到元素{0}", key);
                }
                else
                {
                    Console.WriteLine("在{0}號(hào)位置查到元素{1}", position, key);
                }
                Console.WriteLine("請(qǐng)輸入需要查找的元素或輸入-1退出 ");
                key = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine();
            }
        }
    }