<em id="hanht"></em>

    <dd id="hanht"></dd>

    <em id="hanht"><acronym id="hanht"></acronym></em>
    
    <button id="hanht"></button>
    <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>

    首頁 > 學院 > 邏輯算法 > 正文

    算法系列15天速成 第四天 五大經典查找【上】

    2020-10-08 16:14:38
    字體:
    來源:轉載
    供稿:網友

    在我們的算法中,有一種叫做線性查找。

    分為:順序查找。
            折半查找。

    查找有兩種形態:

    分為:破壞性查找,   比如有一群mm,我猜她們的年齡,第一位猜到了是23+,此時這位mm已經從我腦海里面的mmlist中remove掉了。

                                哥不找23+的,所以此種查找破壞了原來的結構。

           非破壞性查找, 這種就反之了,不破壞結構。

    順序查找:

        這種非常簡單,就是過一下數組,一個一個的比,找到為止。

    復制代碼 代碼如下:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace Sequential
    {
        class Program
        {
            static void Main(string[] args)
            {
                List<int> list = new List<int>() { 2, 3, 5, 8, 7 };

                var result = SequenceSearch(list, 3);

                if (result != -1)
                    Console.WriteLine("3 已經在數組中找到,索引位置為:" + result);
                else
                    Console.WriteLine("嗚嗚,沒有找到!");

                Console.Read();
            }

            //順序查找
            static int SequenceSearch(List<int> list, int key)
            {
                for (int i = 0; i < list.Count; i++)
                {
                    //查找成功,返回序列號
                    if (key == list[i])
                        return i;
                }
                //未能查找,返回-1
                return -1;
            }
        }
    }

    折半查找: 這種查找很有意思,就是每次都砍掉一半,

                 比如"幸運52“中的猜價格游戲,價格在999元以下,1分鐘之內能猜到幾樣給幾樣,如果那些選手都知道折半查找,
                 那結果是相當的啊。

    不過要注意,這種查找有兩個缺點:

                第一: 數組必須有序,不是有序就必須讓其有序,大家也知道最快的排序也是NLogN的,所以.....嗚嗚。
                第二: 這種查找只限于線性的順序存儲結構。

    上代碼:

    復制代碼 代碼如下:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace BinarySearch
    {
        class Program
        {
            static void Main(string[] args)
            {
                List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };

                var result = BinarySearch(list, 45);

                if (result != -1)
                    Console.WriteLine("45 已經在數組中找到,索引位置為:" + result);
                else
                    Console.WriteLine("嗚嗚,沒有找到!");

                Console.Read();
            }

            ///<summary>
    /// 折半查找
    ///</summary>
    ///<param name="list"></param>
    ///<returns></returns>
            public static int BinarySearch(List<int> list, int key)
            {
                //最低線
                int low = 0;

                //最高線
                int high = list.Count - 1;

                while (low <= high)
                {
                    //取中間值
                    var middle = (low + high) / 2;

                    if (list[middle] == key)
                    {
                        return middle;
                    }
                    else
                        if (list[middle] > key)
                        {
                            //下降一半
                            high = middle - 1;
                        }
                        else
                        {
                            //上升一半
                            low = middle + 1;
                        }
                }
                //未找到
                return -1;
            }
        }
    }

    先前也說過,查找有一種形態是破壞性的,那么對于線性結構的數據來說很悲慘,因為每次破壞一下,

    可能都導致數組元素的整體前移或后移。

        所以線性結構的查找不適合做破壞性操作,那么有其他的方法能解決嗎?嗯,肯定有的,不過要等下一天分享。

    ps:  線性查找時間復雜度:O(n);
             折半無序(用快排活堆排)的時間復雜度:O(NlogN)+O(logN);
             折半有序的時間復雜度:O(logN);

    發表評論 共有條評論
    用戶名: 密碼:
    驗證碼: 匿名發表
    一级特黄大片欧美久久久久_一本一道久久综合狠狠老_JLZZ日本人年轻护士_欧美男男作爱VIDEOS可播放
      <em id="hanht"></em>

      <dd id="hanht"></dd>

      <em id="hanht"><acronym id="hanht"></acronym></em>
      
      <button id="hanht"></button>
      <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>