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

2024-11-30 03:36:35

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

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

查找有两种形态：

分为：破坏性查找，比如有一群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);

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

大家是否感觉到,树在数据结构中大行其道,什么领域都要沾一沾,碰一碰.就拿我们前几天学过的排序就用到了堆和今天讲的"二叉排序树",所以偏激的说,掌握的树你就是牛人了. 今天就聊聊这个"五大经典查找"中的最后一个"二叉排序树". 1. 概念: <1> 其实很简单,若根节点有左子树,则左子树的所有节点都比根节点小. 若根节点有右子树,则右子树的所有节点都比根节点大. &
算法系列15天速成第十四天图【上】

今天来分享一下图,这是一种比较复杂的非线性数据结构,之所以复杂是因为他们的数据元素之间的关系是任意的,而不像树那样被几个性质定理框住了,元素之间的关系还是比较明显的,图的使用范围很广的,比如网络爬虫,求最短路径等等,不过大家也不要胆怯, 越是复杂的东西越能体现我们码农的核心竞争力. 既然要学习图,得要遵守一下图的游戏规则. 一: 概念图是由"顶点"的集合和"边"的集合组成.记作:G=(V,E): <1> 无向图就是"图"中的边没
算法系列15天速成第三天七大经典排序【下】

直接插入排序: 这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后, 扑克梳理完毕,4条3,5条s,哇塞...... 回忆一下,俺们当时是怎么梳理的. 最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去, 第五张牌又是3,狂喜,哈哈,一门炮就这样产生了. 怎么样,生活中处处都是算法,早已经融入我们的生活和血液. 下面就上图说明: 看这张图不知道大家可
算法系列15天速成第十一天树操作（上）

先前我们讲的都是"线性结构",他的特征就是"一个节点最多有一个"前驱"和一个"后继".那么我们今天讲的树会是怎样的呢? 我们可以对"线性结构"改造一下,变为"一个节点最多有一个"前驱"和"多个后继".哈哈,这就是我们今天说的"树". 一: 树我们思维中的"树"就是一种枝繁叶茂的形象,那么数据结构中的"树"该
算法系列15天速成——第十五天图【下】（大结局）

今天是大结局,说下"图"的最后一点东西,"最小生成树"和"最短路径". 一: 最小生成树 1. 概念首先看如下图,不知道大家能总结点什么. 对于一个连通图G,如果其全部顶点和一部分边构成一个子图G1,当G1满足: ① 刚好将图中所有顶点连通.②顶点不存在回路.则称G1就是G的"生成树". 其实一句话总结就是:生成树是将原图的全部顶点以最小的边连通的子图,这不,如下的连通图可以得到下面的两个生成树. ② 对于一个带权的连通图,
算法系列15天速成第二天七大经典排序【中】

首先感谢朋友们对第一篇文章的鼎力支持,感动中....... 今天说的是选择排序,包括"直接选择排序"和"堆排序". 话说上次"冒泡排序"被快排虐了,而且"快排"赢得了内库的重用,众兄弟自然眼红,非要找快排一比高下. 这不今天就来了两兄弟找快排算账. 1.直接选择排序: 先上图: 说实话,直接选择排序最类似于人的本能思想,比如把大小不一的玩具让三岁小毛孩对大小排个序, 那小孩首先会在这么多玩具中找到最小的放在第一位,然后找到次
算法系列15天速成第五天五大经典查找【中】

哈希查找: 对的,他就是哈希查找,说到哈希,大家肯定要提到哈希函数,呵呵,这东西已经在我们脑子里面形成固有思维了.大家一定要知道"哈希"中的对应关系. 比如说: "5"是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个"2",那么此时的"5"和"2"就建立一种对应关系,这种关系就是所谓的"哈希关系",在实际应用中也就形成了"2"是key,"5
算法系列15天速成第七天线性表【上】

哈哈,我们的数据也一样,存在这三种基本关系,用术语来说就是: <1> 线性关系.<2> 树形关系.<3> 网状关系. 一: 线性表 1 概念: 线性表也就是关系户中最简单的一种关系,一对一. 如:学生学号的集合就是一个线性表. 2 特征: ① 有且只有一个"首元素". ② 有且只有一个"末元素".
算法系列15天速成第九天队列

一:概念队列是一个"先进先出"的线性表,牛X的名字就是"First in First Out(FIFO)",生活中有很多这样的场景,比如读书的时候去食堂打饭时的"排队".当然我们拒绝插队. 二:存储结构前几天也说过,线性表有两种"存储结构",① 顺序存储,②链式存储.当然"队列"也脱离不了这两种服务,这里我就分享一下"顺序存储". 顺序存储时,我们会维护一个叫做"head头
算法系列15天速成第一天七大经典排序【上】

针对现实中的排序问题,算法有七把利剑可以助你马道成功. 首先排序分为四种: 交换排序: 包括冒泡排序,快速排序. 选择排序: 包括直接选择排序,堆排序. 插入排序: 包括直接插入排序,希尔排序. 合并排序: 合并排序. 那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点,我们设计算法来跟类库提供的快排较量较量.争取KO对手. 冒泡排序: 首先我们自己来设计一下"冒泡排序",这种排序很现实的例子就是:我抓一
算法系列15天速成第十二天树操作【中】

先前说了树的基本操作,我们采用的是二叉链表来保存树形结构,当然二叉有二叉的困扰之处,比如我想找到当前结点的"前驱"和"后继",那么我们就必须要遍历一下树,然后才能定位到该"节点"的"前驱"和"后继",每次定位都是O(n),这不是我们想看到的,那么有什么办法来解决呢? (1) 在节点域中增加二个指针域,分别保存"前驱"和"后继",那么就是四叉链表了,哈哈,还是有点浪费空
算法系列15天速成第十天栈

一: 概念栈,同样是一种特殊的线性表,是一种Last In First Out(LIFO)的形式,现实中有很多这样的例子, 比如:食堂中的一叠盘子,我们只能从顶端一个一个的取. 二:存储结构 "栈"不像"队列",需要两个指针来维护,栈只需要一个指针就够了,这得益于栈是一种一端受限的线性表. 这里同样用"顺序结构"来存储这个"栈",top指针指向栈顶,所有的操作只能在top处. 代码段: 复制代码代码如下: #region
算法系列15天速成第八天线性表【下】

一:线性表的简单回顾上一篇跟大家聊过"线性表"顺序存储,通过实验,大家也知道,如果我每次向顺序表的头部插入元素,都会引起痉挛,效率比较低下,第二点我们用顺序存储时,容易受到长度的限制,反之就会造成空间资源的浪费. 二:链表对于顺序表存在的若干问题,链表都给出了相应的解决方案. 1. 概念:其实链表的"每个节点"都包含一个"数据域"和"指针域". "数据域"中包含当前的数据. "指针域"
算法系列15天速成——第十三天树操作【下】

听说赫夫曼胜过了他的导师,被认为"青出于蓝而胜于蓝",这句话也是我比较欣赏的,嘻嘻. 一概念了解"赫夫曼树"之前,几个必须要知道的专业名词可要熟练记住啊. 1: 结点的权 "权"就相当于"重要度",我们形象的用一个具体的数字来表示,然后通过数字的大小来决定谁重要,谁不重要. 2: 路径树中从"一个结点"到"另一个结点"之间的分支. 3: 路径长度一个路径上的分支数量. 4: 树

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

相关推荐

随机推荐

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