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

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

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

查找有两种形态：

分为：破坏性查找，   比如有一群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)
        {
            Listint> list = new Listint> () { 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(Listint> 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)
        {
            Listint> list = new Listint> () { 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(Listint> 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：  线性查找@R_183_1304@：O(n);
         折半无序（用快排活堆排）的时间复杂度：O(NlogN)+O(logN);
         折半有序的时间复杂度：O(logN);

• 算法系列15天速成 第十四天 图【上】
• 算法系列15天速成——第十三天 树操作【下】
• @L_406_4@
• 算法系列15天速成 第十一天 树操作（上）
• 算法系列15天速成 第十天 栈
• 算法系列15天速成 第八天 线性表【下】
• 算法系列15天速成 第九天 队列
• 算法系列15天速成 第七天 线性表【上】
• 算法系列15天速成 第六天 五大经典查找【下】
• 算法系列15天速成 第五天 五大经典查找【中】
• 算法系列15天速成 第三天 七大经典排序【下】
• 算法系列15天速成 第二天 七大经典排序【中】
• 算法系列15天速成 第一天 七大经典排序【上】
• 算法系列15天速成——第十五天 图【下】（大结局）

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！