蝙蝠岛资源网 Design By www.hbtsch.com

在我们的算法中,有一种叫做线性查找。

分为:顺序查找。
        折半查找。

查找有两种形态:

分为:破坏性查找,   比如有一群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;
        }
    }
}

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

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

             比如"幸运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;
        }
    }
}

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

先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,

可能都导致数组元素的整体前移或后移。

    所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。

ps:  线性查找时间复杂度:O(n);
         折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);
         折半有序的时间复杂度:O(logN);

标签:
经典查找

蝙蝠岛资源网 Design By www.hbtsch.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
蝙蝠岛资源网 Design By www.hbtsch.com

评论“算法系列15天速成 第四天 五大经典查找【上】”

暂无算法系列15天速成 第四天 五大经典查找【上】的评论...

《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。